0
$\begingroup$

G is a context free grammar which all productions are of the form

  1. $X \to aY$
    or
  2. $X \to a$
    Where X, Y are nonterminal and a is nonempty terminal string.

How can I prove it is a type 3 grammar?

  • 0
    Oops: I missed the fact that $a$ was a terminal *string*. When I thought that it was a single terminal character, the obvious interpretation of your question was that you needed to convert from right to left regular. Now @Rick Decker’s interpretation seems more likely, so I’m deleting my answer.2012-09-24

1 Answers 1

0

There are equivalent definitions of a type 3 grammar. One is Brian's left-linear grammar, another is that in a type 3 grammar, all the productions are of the form you listed, along with those of the form $X\rightarrow \lambda$ for some nonterminal $X$. If that's the case, you're done, so I guess you might be working with the definition that says that all productions in a type 3 grammar must be of the form

  1. $X\rightarrow\lambda$
  2. $X\rightarrow a$
  3. $X\rightarrow Y$
  4. $X\rightarrow aY$

where $X, Y$ are nonterminals and $a$ is a single terminal. In your grammar, the productions are restricted to be of the form $X\rightarrow\alpha$ and $X\rightarrow\alpha Y$, where $\alpha$ is a nonempty string of terminals.

Consider a production $X\rightarrow\alpha$ in your grammar, and let $\alpha = a_1a_2\dots a_n$, where the $a_i$ are single characters. Then, you can introduce new variables $X_1, X_2, \dots X_{n-1}$ and replace the production $X\rightarrow\alpha$ with $ X\rightarrow a_1X_1,\quad X_1\rightarrow a_2X_2,\quad\dots,\quad X_{n-1}\rightarrow a_n $ It's clear that these new productions will be equivalent to $X\rightarrow\alpha$. It's easy enouugh to see how to do the same thing to all your productions of the form $X\rightarrow\alpha Y$.

  • 0
    It wouldn’t surprise me if only (1), (2), and (4) are allowed, but that doesn’t affect the answer.2012-09-24