|Regular grammar from CFG? email@example.com (Lorin Netsch) (2004-09-03)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (Eric Bodden) (2004-09-07)|
|Re: Regular grammar from CFG? email@example.com (2004-09-07)|
|Re: Regular grammar from CFG? brosgol@worldDOTstd.com (Ben Brosgol) (2004-09-08)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (2004-09-08)|
|Re: Regular grammar from CFG? email@example.com (Friedrich Neurauter) (2004-09-08)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (Carl Cerecke) (2004-09-08)|
|Re: Regular grammar from CFG? email@example.com (2004-09-13)|
|Re: Regular grammar from CFG? firstname.lastname@example.org (2004-09-13)|
|From:||Carl Cerecke <email@example.com>|
|Date:||8 Sep 2004 12:06:00 -0400|
|Posted-Date:||08 Sep 2004 12:06:00 EDT|
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
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.
Return to the
Search the comp.compilers archives again.