Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

  1. $X \to aY$
  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?

share|cite|improve this question
Hm ... what is the start variable? $X$? Then $L(G_1) = \{a\}$ is finite, hence regular ... – martini Sep 24 '12 at 20:36
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. – Brian M. Scott Sep 24 '12 at 22:00
up vote 0 down vote accepted

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

share|cite|improve this answer
It wouldn’t surprise me if only (1), (2), and (4) are allowed, but that doesn’t affect the answer. – Brian M. Scott Sep 24 '12 at 22:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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