6
$\begingroup$

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

$\endgroup$
4
  • $\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$ Mar 21 '12 at 12:49
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 1 at 19:23
9
$\begingroup$

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.


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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jul 1 at 19:16
  • $\begingroup$ 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 $\endgroup$
    – Gopi
    Aug 5 at 13:11
  • $\begingroup$ 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. $\endgroup$ Aug 5 at 15:14
  • 1
    $\begingroup$ True, it seems that I missed this! (and so did the author of the question at the time it seems!) $\endgroup$
    – Gopi
    Aug 9 at 8:39
  • $\begingroup$ Now I'm not even sure the beginning is correct (update: actually given your comment it probably isn't) $\endgroup$
    – Gopi
    Aug 9 at 8:40

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.