Re: Regular grammar from CFG?

Lorin Netsch wrote:
> Can anyone tell me how to determine if a given CFG can be represented
> as a regular grammar?
>
> If so, what method can be used to generate the right-linear grammar?

Whether an arbitrary CFG generates a regular language is undecidable.
(Theorem 4.2.2 in Seymour Ginsburg's "The Mathematical Theory of
Context-Free Languages").

The following was listed as an open problem by Ginsburg (in 1966); I'm
not sure if it's still open:

"Let G be an arbitrary [context-free] grammar.  Suppose it is known that
L(G) is regular.  Is it solvable to find a right-linear grammar G' such
that L(G) = L(G')?"

Ben Brosgol
brosgol at gnat.com