Authors
Rohit J Parikh
Publication date
1966/10/1
Journal
Journal of the ACM (JACM)
Volume
13
Issue
4
Pages
570-581
Publisher
ACM
Description
In this report, certain properties of context-free (CF or type 2) grammars are investigated, like that of Chomsky. In particular, questions regarding structure, possible ambiguity and relationship to finite automata are considered. The following results are presented:
- The language generated by a context-free grammmar is linear in a sense that is defined precisely.
- The requirement of unambiguity—that every sentence has a unique phrase structure—weakens the grammar in the sense that there exists a CF language that cannot be generated unambiguously by a CF grammar.
- The result that not every CF language is a finite automaton (FA) language is improved in the following way. There exists a CF language L such that for any L′ ⊆ L, if L′ is FA, an L″ ⊆ L can be found such that L″ is also FA, L′ ⊆ L″ and L″ contains infinitely many sentences not in L′.
- A type of grammar is defined that is intermediate …
Total citations
Scholar articles
RJ Parikh - Journal of the ACM (JACM), 1966