Greibach Normal Form

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...

theory, a

context-free grammar In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...

is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a

terminal symbol In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ...

, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the

empty word In formal language theory, the empty string, or empty word, is the unique string of length zero. Formal theory Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special case ...

(epsilon, ε) to be a member of the described language. The normal form was established by

Sheila Greibach Sheila Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...

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 In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ...

a

is a terminal symbol,

A_1 A_2 \ldots A_n

is a (possibly empty) sequence of nonterminal symbols not including the start symbol and

S

is the start symbol. Observe that the grammar does not have

left recursion In the formal language theory of computer science, left recursion is a special case of recursion where a string i