Re: Q: CFG and regular languages

"A Johnstone" <>
25 Sep 2002 23:55:42 -0400

          From comp.compilers

Related articles
Q: CFG and regular languages (Salvador Valerio Cavadini) (2002-09-22)
Re: Q: CFG and regular languages (A Johnstone) (2002-09-25)
Re: Q: CFG and regular languages (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 (Paolo Bonzini) (2002-09-29)
Re: Q: CFG and regular languages (Mark) (2002-09-29)
| List of all articles for this month |

From: "A Johnstone" <>
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 <> 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 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.