Linear Indexed Languages
Linear Indexed Languages
复制标题
线性索引语言
DOI：
10.1016/0304-3975(84)90023-9
复制
发表时间：
1984
影响因子：
1.1
通讯作者：
Rainer Parchmann
中科院分区：
文献类型：
--
作者：
J. Duske;Rainer Parchmann
本文给出了一种基于上下文无关语言控制线性上下文无关文法的线性索引语言的表征和一种基于上下文无关语言同态图像的线性索引语言表征。通过为线性索引语言族构建一个生成器，表明该族是一个完整的半 AFL。此外，还提出了线性索引语言的 Parikh 定理，这意味着存在非线性的索引语言。
In this paper one characterization of linear indexed languages based on controlling linear context-free grammars with context-free languages and one based on homomorphic images of context-free languages are given. By constructing a generator for the family of linear indexed languages, it is shown that this family is a full principal semi-AFL. Furthermore a Parikh theorem for linear indexed languages is stated which implies that there are indexed languages which are not linear.