Access Restriction

Author Parikh, Rohit J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1966
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract 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 $\textit{L}$ such that for any $\textit{L′}$ ⊆ $\textit{L},$ if $\textit{L′}$ is FA, an $\textit{L″}$ ⊆ $\textit{L}$ can be found such that $\textit{L″}$ is also FA, L′ ⊆ $\textit{L″}$ and $\textit{L″}$ contains infinitely many sentences not in $\textit{L′}.A$ type of grammar is defined that is intermediate between type 1 and type 2 grammars. It is shown that this type of grammar is essentially stronger than type 2 grammars and has the advantage over type 1 grammars that the phrase structure of a grammatical sentence is unique, once the derivation is given.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1966-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 13
Issue Number 4
Page Count 12
Starting Page 570
Ending Page 581

Open content in new tab

   Open content in new tab
Source: ACM Digital Library