[Solved]: Can every linear grammar be converted to Greibach form?

Problem Detail: 

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

Asked By : Gigili

Answered By : Gopi

The more general answer is:

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/588