Re: Is this a regular grammar?

The problem with the language is that it has an internal recursion--
that is a recursion which is neither left-recursive nor
right-recursive but has symbols on both sides of the recursive symbol.
Unfortunately, I don't know the official terminology for it. these
are the types of recursions which represent parenthesis.


In your grammar, it involves the rules:


<noun phrase> ::= <determiner><noun>|<determiner><noun><relative clause>


<relative clause> ::= that <noun phrase><verb phrase>


Thus, your language has balance pairs of "<determiner><noun>that" and
"<verb phrase>" surrounding the nested noun phrase. All languages
which have nested pairs like that are not regular (as they require a
stack to keep track of the nesting depth). I believe the terminology
for languages consisting only of such pairs is Dyke languages (perhaps
spelled differently as I have never seen the word in print only heard
it with my ears, presumably after the person who discovered or
formalized them).


If you need a more formal proof, you will have to wait until someone
with a more academic bent posts. One method of doing so, is to assume
that you have a machine of finite size n and show that with a stack
depth of m, such that n < m, the machine must use one state for two
different nestings and thus must either accept some string not in the
language or reject some string within the language.


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: compres@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847
--

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