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 you can show that a CFG C is deterministic (non-ambiguous), then it
is possible to answer whether L is regular (where L is the language
generated by C).


It is necessary to show that, for all nonterminals A in C, there are no
derivations A -*-> alpha A beta (where the length of alpha and beta are
  > 0). In other words, middle-recursive grammatical structures such as
the nesting of parentheses in an arithmetic expression are not regular.


I think that this condition may also be sufficient, but I'm not sure
without a bit more investigation.


Hopcroft and Ullman (1979) note that "The proof is lengthy and the
reader is referred to Stearns (1967) or Valiant (1975b)"


Stearns: "A regularity test for pushdown machines", Information and
Control 11: 3, 323-340


and


Valiant: "Regularity and related problems for deterministic pushdown
automata", JACM 22: 1, 1-10


I haven't read either paper, sorry. The full text of Valiant is online
at acm.org, but you have to pay for it.


Cheers,
Carl.

Return to the comp.compilers page.
Search the comp.compilers archives again.