Editing Greibach normal form

In [[formal language]] theory, a [[context-free grammar]] is in '''Greibach normal form''' ('''GNF''') if the right-hand sides of all [[production (computer science)|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 recursion]]s.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form.<ref>{{cite journal | last=Greibach | first=Sheila | title=A New Normal-Form Theorem for Context-Free Phrase Structure Grammars |date=January 1965| journal=Journal of the ACM | volume=12| issue=1 | pages=42–52 | doi = 10.1145/321250.321254| s2cid=12991430 | doi-access=free }}</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({{var|n}}<sup>4</sup>) in the general case and O({{var|n}}<sup>3</sup>) if no derivation of the original grammar consists of a single nonterminal symbol, where {{var|n}} is the size of the original grammar.<ref>{{cite journal | first1 = Norbert | last1 = Blum | first2 =  Robert | last2 = Koch | title = Greibach Normal Form Transformation Revisited | journal = Information and Computation | volume = 150 | issue = 1 | year = 1999 | pages = 112–118  | citeseerx = 10.1.1.47.460 | doi=10.1006/inco.1998.2772| s2cid = 10302796 }}</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 {{var|n}}, any [[top-down parsing|top-down parser]] will halt at depth {{var|n}}.

== See also ==
* [[Backus–Naur form]]
* [[Chomsky normal form]]
* [[Kuroda normal form]]

== References ==
<references/>
* {{cite book|author=Alexander Meduna|title=Automata and Languages: Theory and Applications|url=https://books.google.com/books?id=a-rjBwAAQBAJ&q=%22Greibach+normal+form%22|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4471-0501-5}}
* {{cite book|author=György E. Révész|title=Introduction to Formal Languages|url=https://books.google.com/books?id=3s7CAgAAQBAJ&q=%22Greibach+normal+form%22|date=17 March 2015|publisher=Courier Corporation|isbn=978-0-486-16937-8}}

[[Category:Formal languages]]