Type 1 in Finite Space grammar possible?

"Quinn Tyler Jackson" <qjackson@shaw.ca>
3 Sep 2002 00:28:50 -0400

          From comp.compilers
Related articles
Type 1 in Finite Space grammar possible? qjackson@shaw.ca (Quinn Tyler Jackson) (2002-09-03)
| List of all articles for this month |
From: "Quinn Tyler Jackson" <qjackson@shaw.ca>
Newsgroups: comp.compilers
Date: 3 Sep 2002 00:28:50 -0400
Organization: Compilers Central
Keywords: parse, question
Posted-Date: 03 Sep 2002 00:28:50 EDT

The language $:


(A[n] x is a[n] y.)+ Is a[n] x-sub-n a[n] y-sub-n?


Example:


"A dog is an animal. A car is a vehicle. A computer is a machine. Is a
car a vehicle?"


But not:


"A dog is an animal. A car is a vehicle. A computer is a machine. Is a
computer an animal?"


(Note that the final question is only accepted if the x-y pair correlates.)


The question:


Can a finitely large Type 1 Chomsky form grammar be constructed that
accepts the language $? (It must be entirely expressible by the
grammar, not by external ad hockery.)


--
Quinn Tyler Jackson
http://members.shaw.ca/qjackson/

Post a followup to this message

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