Re: Is this a regular grammar?

David L Moore <dlmoore@ix.netcom.com>
3 Nov 1997 21:00:34 -0500

          From comp.compilers

Related articles
Is this a regular grammar? smecucci@mbox.thunder.it (Silvio Mecucci) (1997-11-02)
Re: Is this a regular grammar? dlmoore@ix.netcom.com (David L Moore) (1997-11-03)
Re: Is this a regular grammar? clark@quarry.zk3.dec.com (1997-11-03)
| List of all articles for this month |

From: David L Moore <dlmoore@ix.netcom.com>
Newsgroups: comp.compilers
Date: 3 Nov 1997 21:00:34 -0500
Organization: Netcom
References: 97-11-016
Keywords: parse, theory

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.
--


Post a followup to this message

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