Caterpillars and Context-Free Languages
Caterpillars and Context-Free Languages
复制标题
毛毛虫和上下文无关语言
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
B. Monien
中科院分区：
文献类型：
--
作者：
M. Chytil;B. Monien
我们使用毛毛虫树的概念来研究无上下文语言的属性，特别是有关无上下文语言索引的新结果，并以这种方式获得了无上下文语言的识别。第一组结果表明，模棱两可和明确的语言之间的差异。对于明确的语言，我们证明有限索引和O（log n）索引之间存在差距。对于模棱两可的语言，没有这样的差距：我们证明了具有无限但任意缓慢生长索引的语法存在。我们表明，有限语言是有限索引，并给出确定性的日志空间算法，以识别确定性有限索引语言。我们还描述了一种并行算法，以识别使用o（n2）处理器O（log2n）的机组人员上的确定性上下文语言。
We use the concept of a caterpillar tree to study the properties of context-free languages, in particular new results about the index of context-free languages and the recognition of context-free languages are obtained this way. The first group of results points to differences between ambiguous and unambiguous languages. For unambiguous languages we prove the existence of a gap between finite index and O(log n) index. For ambiguous languages there is no such a gap: we prove the existence of grammars with infinite but arbitrarily slowly growing index. We show that bounded languages are of finite index and give a deterministic log space algorithm for the recognition of deterministic finite index languages. We also describe a parallel algorithm recognizing deterministic context-free languages on a CREW-PRAM with O(n2) processors in time O(log2n).