# Prove that L(G1) is a regular language

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?

-
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

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

-
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