Re: Regular Language

nospam411@my-deja.com
27 Jul 2000 21:38:46 -0400

          From comp.compilers
Related articles
Regular Language thomaspan2000@aol.com (2000-07-23)
Re: Regular Language nospam411@my-deja.com (2000-07-27)
Re: Regular Language vannoord@let.rug.nl (2000-07-29)
| List of all articles for this month |
From: nospam411@my-deja.com
Newsgroups: comp.compilers
Date: 27 Jul 2000 21:38:46 -0400
Organization: Deja.com - Before you buy.
References: 00-07-045
Keywords: parse, theory

I suppose if you can show that the language grammar has a production
of the form


A->BC,
where B and C are non-terminals you have your proof. Regular
languages have to have no more than a single non terminal on
either side in any production in the grammar, going by
chomsky's hierarchy.


    thomaspan2000@aol.com (Thomaspan2000) wrote:
> Currently, I use lex and yacc to write a parser for a C-like
language. The
> problem is I want to know whether it is regular or not. Since it
contains
> if ...
> else if ...
> ...
> else ...
> it is not a regular language. But how to prove? I know lex and yacc
generates
> LALR language and there is also a pumping lemma for regular sets. But
how to
> prove one language is not regular language?

Post a followup to this message

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