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

ignougroup
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. $Xrightarrow 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