In computer science and formal language theory, a context-free grammar is in Greibach normal form if the right-hand sides of all productions start with a terminal symbol, optionally followed by some variables. 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 bears the name of Sheila Greibach.
More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:
or
where A is a nonterminal symbol, α is a terminal symbol, is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and ε is the empty word.
Observe that the grammar must be without left recursions.
Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. (Some definitions do not consider the second form of rule to be permitted, in which case a context-free grammar that can generate the empty word cannot be so transformed.) In particular, there is a construction ensuring that the resulting normal form grammar is of size at most O(n4), where n is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton.
Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n.
Famous quotes containing the words normal and/or form:
“To try to control a nine-month-old’s clinginess by forcing him away is a mistake, because it counteracts a normal part of the child’s development. To think that the child is clinging to you because he is spoiled is nonsense. Clinginess is not a discipline issue, at least not in the sense of correcting a wrongdoing.”
—Lawrence Balter (20th century)
“Freedom of religion, freedom of the press, and freedom of person under the protection of habeas corpus, and trial by juries impartially selected. These principles form the bright constellation which has gone before us, and guided our steps through an age of revolution and reformation.”
—Thomas Jefferson (1743–1826)