Greibach Normal Form

Greibach Normal Form: In Chomsky’s Normal Form (CNF), restrictions are put on the length of right sides of a production, whereas in Greibach Normal Form (GNF), restriction are put on the positions in which terminals and variables can appear. GNF is useful in simplifying some proofs and making constructions such as Push Down Automaton (PDA) accepting a CFG.

Definition: A context-free grammar is said to be in Greibach Normal Form (GNF) if all productions have the form

A-> ax,

where a ÎT and x ÎV * .

For a grammar in GNF, the RHS of every production has a single terminal followed by a string of variables.

The procedure of getting a grammar in GNF is beyond the scope of this book.

GLOSSARY

CFG: Context-Free Grammar.

Left-Linear Grammar: All productions are either of the form

V ->VT *

or V ->T *

Right-Linear Grammar: All productions are either of the form

V->T *V

or V->T *

Parsing: Finding a derivation of the string.

Topdown Parsing: Sequence of rules applied in the leftmost derivation

Bottomup Parsing: Sequence of rules applied in a rightmost derivation.

Ambiguous Grammar: A CFG is said to be “ambiguous” if there exists at least one string in the language of the CFG which is ambiguously derivable. Otherwise it is unambiguous.

Useless Production: A production rule not affecting the language

Unit Production: Any production of a CFG of the form A® B where A, B ÎV is called a Unit-Production.

Chomsky Normal Form: A CFG without any l-productions is generated by a grammar in which productions are of the form A® BC or A® a, where A, BÎVN and a VT Î .