Re: Making an NFA from a grammar

vannoord@let.rug.nl
18 Aug 2001 00:41:36 -0400

          From comp.compilers
Related articles
Making an NFA from a grammar meson@cyber.net.pk (2001-08-02)
Re: Making an NFA from a grammar martijn@shop.com (Martijn de Vries) (2001-08-15)
Re: Making an NFA from a grammar joachim_d@gmx.de (Joachim Durchholz) (2001-08-17)
Re: Making an NFA from a grammar vannoord@let.rug.nl (2001-08-18)
| List of all articles for this month |
From: vannoord@let.rug.nl
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 <meson@cyber.net.pk> 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.


@Article{markjan-cl2000,
    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 http://www.let.rug.nl/~vannoord

Post a followup to this message

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