Formal language theory: refining the Chomsky hierarchy
Formal language theory: refining the Chomsky hierarchy
复制标题
DOI：
10.1098/rstb.2012.0077
复制
发表时间：
2012-07-19
影响因子：
6.3
通讯作者：
Rogers, James
中科院分区：
文献类型：
--
作者：
Jaeger, Gerhard;Rogers, James
本文的第一部分简要介绍了Chomsky层次结构的四个层次，特别强调了上下文无关语言和正则语言。然后，它概括的参数，为什么没有定期或上下文无关的语法是足够的表达，以捕捉自然语言语法中的所有现象。在第二部分中，Chomsky层次结构的两个改进，这两个改进都与认知科学中现存的研究有关：轻度上下文敏感语言（位于上下文无关语言和上下文敏感语言之间）和次正则层次结构（区分正则语言类中的几个复杂性级别）。
The first part of this article gives a brief overview of the four levels of the Chomsky hierarchy, with a special emphasis on context-free and regular languages. It then recapitulates the arguments why neither regular nor context-free grammar is sufficiently expressive to capture all phenomena in the natural language syntax. In the second part, two refinements of the Chomsky hierarchy are reviewed, which are both relevant to the extant research in cognitive science: the mildly context-sensitive languages (which are located between context-free and context-sensitive languages), and the sub-regular hierarchy (which distinguishes several levels of complexity within the class of regular languages).