Greibach normal form

Revision as of 11:39, 1 May 2025 by 131.111.5.201 (talk)
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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:

<math>A \to a A_1 A_2 \cdots A_n</math>

where <math>A</math> is a nonterminal symbol, <math>a</math> is a terminal symbol, and <math>A_1 A_2 \ldots A_n</math> 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.<ref>Template:Cite journal</ref> 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:Var4) in the general case and O(Template:Var3) if no derivation of the original grammar consists of a single nonterminal symbol, where Template:Var is the size of the original grammar.<ref>Template:Cite journal</ref> 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.

See alsoEdit

ReferencesEdit

<references/>