Show that a Language can be Generated by a regular grammar I'm looking for hints on the following exercise from Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.


  Let $G$ be a grammar where all the productions are of the form $A\to xB$ and $A\to x$, where $A$ and $B$ are single variables and $x$ is a string of terminals. Show that $L(G)$ can be generated by a regular grammar.


This is from the second chapter of the book, so the solution should just require grammars (automata don't appear until chapter 3).

I assume that "Show that $L(G)$ can be generated by a regular grammar" means that I have to show the language generated, since this can be shown as regular grammar just by pointing out the productions.

This is where I get a bit confused...

Edit: Wrong usage of production so this is wrong, therefore what i did below is the wrong way to tackle this exercise

If i start doing the productions:
\begin{align*}
A&amp;\to xB\\
\text{(with second)} A&amp;\to AB\\ 
\text{(with  first)} A&amp;\to xBB
\end{align*}
And so on... so in the (n)th step
$A^* → x^{n-1}B^n$ Since There would always be one $B$ more than $x$.

I was thinking that maybe I could change $xB$ for $A$ then for $x$ again to have just the string of terminals $x$ resulting in what the language generates, and this is where I think I am probably not understanding something right. I assume I am wrong because there cant be a non terminal when generating a Language...Right? Or am I just doing it all wrong?

Thank you for your time. I'm learning in Japan and my professor's English isn't very good so I can't ask him.
The only thing that prevents your grammar from being a regular grammar is that $x$ is a string rather than a single terminal. That means that you have to deal with two kinds of problems:


$x$ is a string containing more than one terminal.
$x$ is the empty string.


To deal with the first problem, replace each problematic rule by a chain of equivalent rules of the proper form. For example, $A \to \alpha \beta$ is the same as $A \to \alpha X$ and $X \to \beta$.

To deal with the second problem, you have to get rid of rules of the form $A\to B$ and of rules of the form $A \to \epsilon$. Hopefully this is something you already know how to do. If not, notice that $A \to B$ means that whenever you have $A$, you can replace it with $B$, and $A \to \epsilon$ means that whenever you have $A$, you can remove it. Doing so recursively will allow you to get rid of these rules.