# Can every linear grammar be converted to Greibach form?

Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$?

($T$ is the set of terminals, $V$ is the set of non-terminals, $\lambda$ is the empty sequence.)

• Yes, it is one of the “normal forms”. But there may be an issue with left recursion, have to check. – uli Mar 21 '12 at 7:25
• Your notation isn't entirely clear to me. Is $T$ the set of terminals and $V$ the non-terminals, or $V$ the vocabulary and $T$ the rules? – arnsholt Mar 21 '12 at 8:52
• Every grammar can be converted to a GNF, but the GNF is more general than your definition. I've edited your question to define the notations, please check that this is what you meant. – Gilles 'SO- stop being evil' Mar 21 '12 at 12:49

Blum and Koch showed a polynomial time transformation such that any context-free grammar can be converted to Greibach form.

Since a linear grammar is a special case of Context-free grammar, the answer is yes.

A simpler transformation:

• Any rule $X \rightarrow a_1 a_2 \cdot a_k Y$ you transform them in $k$ rules:

1. $X\rightarrow a_1 X_1Y$.
2. $\cdots$
3. $X_{i-1}\rightarrow a_{i}X_i$
4. $X_{k-1}\rightarrow a_{k}Y$
• Any rule $X \rightarrow a Y b$ should be transformed in two rules

1. $X \rightarrow a Y Y_1$.
2. $Y_1 \rightarrow b$

where the capital letters belong to $V$ and the small letters to the alphabet (terminals).