Is this a regular grammar?

Silvio Mecucci <smecucci@mbox.thunder.it>
2 Nov 1997 23:12:42 -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: Silvio Mecucci <smecucci@mbox.thunder.it>
Newsgroups: comp.compilers
Date: 2 Nov 1997 23:12:42 -0500
Organization: Compilers Central
Keywords: parse, theory, question, comment

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


This is an excercise from "Fromal Syntax of programming languages"
Slonneger, K.; Kurtz, B. L.:
I'd like to see the solution!


--
Silvio Mecucci, Dpt. of Chemistry, Columbia University
3000 Broadway, Mail Code 3153, New York, N.Y. 10027
Tel. +1 212 854 8402, 854 5143
[He promises it's not a homework assignment. -John]
--

Post a followup to this message

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