An Hierarchy Between Context-Free and Context-Sensitive Languages
An Hierarchy Between Context-Free and Context-Sensitive Languages
复制标题
上下文无关语言和上下文相关语言之间的层次结构
DOI：
10.1016/s0022-0000(70)80045-9
复制
发表时间：
1970
期刊：
影响因子：
--
通讯作者：
T. Kasai
中科院分区：
文献类型：
--
作者：
T. Kasai
引入由上下文相关语言组成的语族的无限子族ℒ1、ℒ2...、ℒ∞、ℒω，使得ℒ1C≠ℒ2C≠⋯C≠ℒ∞ℒω，其中ℒ1是ε无关的上下文无关语言族，ℒω是上下文相关语言族，并且每个ℒ都是一个抽象语言族，即，在 +、·、U、逆同态、无 ε 同态以及与正则集的交集下闭合。 ℒ 的每种语言都由称为状态语法的语法定义，可以将其视为具有状态的上下文无关语法。
Infinite subfamilies ℒ1, ℒ2..., ℒ∞, ℒωof the family consisting of contextsensitive languages, are introduced such that ℒ1C≠ℒ2C≠⋯C≠ℒ∞ℒω, where ℒ1is the family of ∈-free context-free languages, ℒωis the family of context-sensitive languages, and each ℒnis an Abstract Family of Languages, i.e., closed under +, ·, U, inverse-homomorphism, ∈-free homomorphism, and intersection with regular sets. Each language of ℒnis defined by a grammar, called a state grammar, that may be thought of as a context-free gramma with states.