# 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, 2012 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? Mar 21, 2012 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. Mar 21, 2012 at 12:49
• Note that linear grammars that are restricted to the form you propose, $A\to aB$ or $A\to a$ are so-called right-linear grammars, and generate exactly the regular languages. This means that the linear language $\{a^nb^n\mid n\ge 1\}$ cannot be generated by a grammar which is both linear and in Greibach normal form. Jul 1, 2021 at 19:23

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.

EDIT: the rest of this answer is out of scope since the question was about Linear GNF and not just GNF (thanks @hendrik-jan for spotting this)

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).

• The simpler transformation proposed here does not take into account productions that are left-recursive, i.e., of the form $A\to Ba$. Also, the second case does introduce a rule $X\to aYY_1$, which is not linear. Jul 1, 2021 at 19:16
• True, missing $A\rightarrow Ba$: you can transform in $A\rightarrow B \tilde{A}$ and $\tilde{A}\rightarrow a$. As for $X \rightarrow a YY_1$, it is not meant to be linear but GNF
– Gopi
Aug 5, 2021 at 13:11
• Thanks for reacting, even for such an old question. What I mean is: the result is GNF, but not necessarily in "linear GNF", as specified in the question. Aug 5, 2021 at 15:14
• True, it seems that I missed this! (and so did the author of the question at the time it seems!)
– Gopi
Aug 9, 2021 at 8:39
• Now I'm not even sure the beginning is correct (update: actually given your comment it probably isn't)
– Gopi
Aug 9, 2021 at 8:40