8 Sep 2004 12:06:00 -0400

Related articles |
---|

Regular grammar from CFG? netsch@ti.com (Lorin Netsch) (2004-09-03) |

Re: Regular grammar from CFG? newsserver_mails@bodden.de (Eric Bodden) (2004-09-07) |

Re: Regular grammar from CFG? vannoord@let.rug.nl (2004-09-07) |

Re: Regular grammar from CFG? brosgol@worldDOTstd.com (Ben Brosgol) (2004-09-08) |

Re: Regular grammar from CFG? vbdis@aol.com (2004-09-08) |

Re: Regular grammar from CFG? friedrich.neurauter@eunet.at (Friedrich Neurauter) (2004-09-08) |

Re: Regular grammar from CFG? cdc@maxnet.co.nz (Carl Cerecke) (2004-09-08) |

Re: Regular grammar from CFG? neal.wang@gmail.com (2004-09-13) |

Re: Regular grammar from CFG? scavadini@ucse.edu.ar (2004-09-13) |

From: | Carl Cerecke <cdc@maxnet.co.nz> |

Newsgroups: | comp.compilers |

Date: | 8 Sep 2004 12:06:00 -0400 |

Organization: | TelstraClear |

References: | 04-09-035 |

Keywords: | parse, theory |

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

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.