Following is a problem that I have no idea how to solve. I'd appreciate someone showing me how to solve this problem.
A CFG is right-linear if each production body has at most one variable, and that variable is at the right end; i.e. all productions of a right-linear grammar are of form $A\rightarrow wB$ or $A\rightarrow w$, where $A$ and $B$ are variables and $w$ is some string of zero or more terminals.
Show that every right-linear grammar generates a regular language. (Hint: construct an $\epsilon$-NFA simulating leftmost derivations, using its state to represent the lone variable in the current left-sentential form.)
Show that every regular language has a right-linear grammar. (Hint: start with a DFA and let the variables of the grammar represent states.)
Best Answer
You have to show that for each RLIN grammar you can build a FSA for the language it represents, and vice-versa. Formally that is done by giving a construction. For a RLIN grammar $G$ explicitly give the components of equivalent automaton $\cal A$.
That is not too hard. The two formalisms are actually quite close. The production $A\to wB$ has the same effect as an automaton move $A \overset{w}\to B$. The only problem here is that in the grammar $w$ may consist of several letters, which usually is not allowed for automata.