Re: Q: CFG and regular languages

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

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