Re: Making an NFA from a grammar
18 Aug 2001 00:41:36 -0400

          From comp.compilers

Related articles
Making an NFA from a grammar (2001-08-02)
Re: Making an NFA from a grammar (Martijn de Vries) (2001-08-15)
Re: Making an NFA from a grammar (Joachim Durchholz) (2001-08-17)
Re: Making an NFA from a grammar (2001-08-18)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 18 Aug 2001 00:41:36 -0400
Organization: Faculteit der Letteren, Rijksuniversiteit Groningen, NL
References: 01-08-008 01-08-094
Keywords: parse, theory
Posted-Date: 18 Aug 2001 00:41:36 EDT

compiler <> wrote:
> Is there any algorithm,
> which when given a grammar, converts it back to an NFA, IFF the
> grammar represents a regular language.

No. It is undecidable whether an arbitrary context-free grammar defines
a regular language.

For algorithms which work in particular sub-cases,
refer to the following article.

    author = {Mark-Jan Nederhof},
    title = {Practical Experiments with Regular Approximation of Context-free Languages},
    journal = {Computational Linguistics},
    year = 2000,
    volume = 26,
    number = 1,
    pages = {17--44}

Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl

Post a followup to this message

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