Re: Q: CFG and regular languages

"A Johnstone" <adrian@sartre.cs.rhbnc.ac.uk>
25 Sep 2002 23:55:42 -0400

          From comp.compilers

Related articles
Q: CFG and regular languages scavadini@ucse.edu.ar (Salvador Valerio Cavadini) (2002-09-22)
Re: Q: CFG and regular languages adrian@sartre.cs.rhbnc.ac.uk (A Johnstone) (2002-09-25)
Re: Q: CFG and regular languages hannah@schlund.de (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 bonzini@gnu.org (Paolo Bonzini) (2002-09-29)
Re: Q: CFG and regular languages whopkins@alpha2.csd.uwm.edu (Mark) (2002-09-29)
| List of all articles for this month |

From: "A Johnstone" <adrian@sartre.cs.rhbnc.ac.uk>
Newsgroups: comp.compilers
Date: 25 Sep 2002 23:55:42 -0400
Organization: Royal Holloway, University of London
References: 02-09-132
Keywords: parse, theory
Posted-Date: 25 Sep 2002 23:55:41 EDT

Salvador Valerio Cavadini <scavadini@ucse.edu.ar> 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
but...


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.)


                                                      Adrian


--
Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email a.johnstone@rhul.ac.uk Tel:+44(0)1784 443425 Fax:+44(0)1784 439786


Post a followup to this message

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