[Math] Prove that L(G1) is a regular language

context-free-grammarformal-grammar

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?

Best Answer

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

Related Question