|Q: CFG and regular languages firstname.lastname@example.org (Salvador Valerio Cavadini) (2002-09-22)|
|Re: Q: CFG and regular languages email@example.com (A Johnstone) (2002-09-25)|
|Re: Q: CFG and regular languages firstname.lastname@example.org (Hannah Schroeter) (2002-09-25)|
|Re: Q: CFG and regular languages debray@CS.Arizona.EDU (Saumya K. Debray) (2002-09-25)|
|Re: Q: CFG and regular languages email@example.com (Paolo Bonzini) (2002-09-29)|
|Re: Q: CFG and regular languages firstname.lastname@example.org (Mark) (2002-09-29)|
|From:||"A Johnstone" <email@example.com>|
|Date:||25 Sep 2002 23:55:42 -0400|
|Organization:||Royal Holloway, University of London|
|Posted-Date:||25 Sep 2002 23:55:41 EDT|
Salvador Valerio Cavadini <firstname.lastname@example.org> wrote:
: I'm looking for an algorithm for determine if a context free grammar
: generates a regular language. Any idea?
: [Hmmn. Would it suffice to check that there's no direct or indirect
: recursion in the rules? -John]
Not sure if this is homework or not, so I won't give a full answer
John's suggestion is too strong: the fundamental difference between
regular and context free languages is that CFGs can describe embedded
recursion, that is bracketing constructs. You can use recursion to
describe repeated sequences of tokens and still have a regular
language. John's suggestion would allow only finite languages.
As a way in to your problem, you might find it useful to convert your
CFG into Chomsky normal form. Look up regular grammars in a formal
languages book and you'll see that they look like CFGs with an
ordering constraint on the relationships between the rules. (Hope
that's not too cryptic.)
Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email email@example.com Tel:+44(0)1784 443425 Fax:+44(0)1784 439786
Return to the
Search the comp.compilers archives again.