Greibach normal form

Template:Short description In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some non-terminals. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.

More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:

$A\to a{A}_1{A}_2\cdots A_n$

where $A$ is a nonterminal symbol, $a$ is a terminal symbol, and $A_1{A}_2\dots A_n$ is a (possibly empty) sequence of nonterminal symbols.

Observe that the grammar does not have left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. Various constructions exist. Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word. For one such construction the size of the constructed grammar is O(Template:Var⁴) in the general case and O(Template:Var³) if no derivation of the original grammar consists of a single nonterminal symbol, where Template:Var is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a real-time (non-deterministic) pushdown automaton, i.e., the automaton reads a letter from its input every step.

Given a grammar in GNF and a derivable string in the grammar with length Template:Var, any top-down parser will halt at depth Template:Var.

Variants of Greibach normal form

It is even possible to convert a grammar into Greibach normal form in a way such that in every production, at most two nonterminal symbols occur on the right-hand side; this is referred to as quadratic Greibach normal form.

A context-free grammar is in double Greibach normal form, if all production rules take one of the two forms:

$A\to a{A}_1{A}_2\cdots A_{n}b$

$A\to a$

where $A$ is a nonterminal symbol, $a,b$ are terminal symbols (not necessarily distinct), and $A_1{A}_2\dots A_n$ is a (possibly empty) sequence of nonterminal symbols. Similarly as above, a grammar is in quadratic double Greibach normal form, if at most two nonterminal symbols occur in the right-hand side of each production. A classic result by Hotz (1978) states that every context-free grammar that does not generate the empty word can be effectively converted into an equivalent grammar in quadratic double Greibach normal form.

See also

• Backus–Naur form
• Chomsky normal form
• Kuroda normal form

References

• Template:Cite book
• Template:Cite book
• Autebert, J. M., Berstel, J., & Boasson, L. (1997). Context-free languages and pushdown automata. In Handbook of Formal Languages: Volume 1 Word, Language, Grammar (pp. 111-174). Berlin, Heidelberg: Springer Berlin Heidelberg.