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

  • $\begingroup$ Yes, it is one of the “normal forms”. But there may be an issue with left recursion, have to check. $\endgroup$ – uli Mar 21 '12 at 7:25
  • $\begingroup$ 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? $\endgroup$ – arnsholt Mar 21 '12 at 8:52
  • $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Mar 21 '12 at 12:49

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.