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
Commented 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? Commented 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. Commented 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. Commented 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. Commented 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
Commented 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. Commented 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
Commented 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
Commented Aug 9, 2021 at 8:40