Re: Is this a regular grammar?

Silvio Mecucci wrote:
>
> Can somebody proof that the language generated by this grammar is NOT a
> regular language ?
>
> <sentence> ::= <noun phrase><verb phrase>.
> <noun phrase> ::= <determiner><noun>|<determiner><noun><relative clause>
> <verb phrase> ::= <verb>|<verb><noun phrase>
> <relative clause> ::= that <noun phrase><verb phrase>
> <noun> ::= boy | girls | cat | telescope | song | feather
> <determiner> ::= a | the
> <verb> ::= saw | touched | surprised |sang


Lets start by simplifying it to:


<sentence> ::= <noun phrase><verb phrase>
<noun phrase> ::= the cat | the cat <relative clause>
<verb phrase> ::= saw | saw <noun phrase>
<relative clause> ::= that <noun phrase> <verb phrase>


S ::= NV
N ::= b | bR
V ::= c | cN
R ::= dNV


It is clear that the original grammar is regular only if this
grammar is regular.


Substituting:


S = NV
N = b | bdNV
V = c | cb | cbdNV = c | cb | cbdb | cbdbdNVV etc.


And here is the problem. We can pump out N->bdNV as often as
desired and we require that there be as many V's as "bd"s. This
cannot be handled by a finite state automaton (just pump
out one more N than there are states in your automaton),
so the language is not regular.


This is usually stated as "FSAs cannot count". The canonical example
is that the language ab aabb aaabbb, etc, with as many a's as b's,
is not regular.


David Moore.
--

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