ON CONTEXT-FREE LANGUAGES
ON CONTEXT-FREE LANGUAGES
复制标题
DOI：
10.1145/321356.321364
复制
发表时间：
1966-01-01
影响因子：
2.5
通讯作者：
PARIKH, RJ
中科院分区：
文献类型：
--
作者：
PARIKH, RJ
在这个报告中，研究了上下文无关（CF或类型2）语法的某些属性，就像乔姆斯基的那样。特别考虑了有关结构、可能的歧义和与有限自动机的关系的问题。结果如下：由上下文无关语法生成的语言在精确定义的意义上是线性的。对无歧义性的要求（即每个句子都有一个独特的短语结构）削弱了语法，因为存在一种CF语言不能由CF语法无歧义地生成。并不是所有CF语言都是有限自动机（FA）语言，这一结论在以下方面得到了改进。存在一种CF语言，使得对于任何一个L’的规模物，如果L’是FA，则L″的规模物，L″也是FA， L’的规模物″和L″包含无限多个非L’的句子。定义了一种介于类型1和类型2之间的语法类型。研究表明，这种类型的语法本质上比类型2语法更强大，并且与类型1语法相比，它的优势在于，一旦给出了推导，语法句子的短语结构是唯一的。
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 languageLsuch that for anyL′⊆L, ifL′is FA, anL″⊆Lcan be found such thatL″is also FA, L′ ⊆L″andL″contains infinitely many sentences not inL′.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.