13 Sep 2004 10:50:17 -0400

Related articles |
---|

[2 earlier articles] |

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: | scavadini@ucse.edu.ar |

Newsgroups: | comp.compilers |

Date: | 13 Sep 2004 10:50:17 -0400 |

Organization: | Compilers Central |

References: | 04-09-035 04-09-042 |

Keywords: | parse, theory, bibliography |

Posted-Date: | 13 Sep 2004 10:50:17 EDT |

*>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?*

A couple of years ago I did the same question in this group.

The problem is undecidable in general: given ANY CFG it's impossible

to determine if the language generated is regular or not.

But there are some particular cases where you can give an answer to

the question (including an equivalent regular grammar), for example:

* if the CF grammar's alphabet is unary, the language is regular

* if the CFG is not self-embedded, the language is regular

Also, there are some special case of self-embedded CFG that generate

regular languages.

You can read the following articles:

* Stefan Andrei, Wei-Ngan Chin, Salvador Valerio Cavadini: Self-embedded

context-free grammars with regular counterparts. Acta Inf. 40(5): 349-365

(2004)

n

* Stefan Andrei, Salvador Valerio Cavadini, Wei-Ngan Chin: A new algorithm

for regularizing one-letter context-free grammars. Theor. Comput. Sci.

306(1-3): 113-122 (2003)

* Stefan Andrei, Salvador Cavadini y Wei-Ngan Chin. "Transforming

self-embedded context-free grammars into regular expressions". Faculty of

Computer Science. TR02-06, http://www.infoiasi.ro/~tr/tr.pl.cgi, Iasi

University, Romania (2002) 1-25.

Regards

Salvador Valerio Cavadini

Centro de Investigación y Desarrollo de Software (CIDESOFT)

Facultad de Matemática Aplicada

Universidad Católica de Santiago del Estero (Argentina)

web: http://www.ucse.edu.ar/fma/staff/svcavadini

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.