GENERALIZATIONS OF REGULAR SETS AND THEIR APPLICATION TO A STUDY OF CONTEXT-FREE LANGUAGES
GENERALIZATIONS OF REGULAR SETS AND THEIR APPLICATION TO A STUDY OF CONTEXT-FREE LANGUAGES
复制标题
DOI：
10.1016/s0019-9958(75)90058-3
复制
发表时间：
1975-01-01
影响因子：
--
通讯作者：
TAKAHASHI, M
中科院分区：
文献类型：
--
作者：
TAKAHASHI, M
我们扩展的概念，经常设置字符串的树木和森林在一个统一的数学方法，并调查他们的属性。然后，通过采取这些对象的某些一维表达式，我们来到一个有趣的CF语言的子类定义对字母表。它们构成了一个以Dyck集为论域的布尔代数，并在整个CF语言类中起着重要的作用。特别是，使用子类，我们证明了著名的Chomsky-Schützenberger定理的改进，并证明了括号语法的决策过程可以扩展到更广泛的CF语法类。
We extend the notion of regular sets of strings to those of trees and of forests in a unified mathematical approach, and investigate their properties. Then by taking certain one-dimensional expressions of these objects, we come to an interesting subclass of CF languages defined over paired alphabets. They are shown to form a Boolean algebra with the Dyck set as the universe, and to play an important role in the whole class of CF languages. In particular, using the subclass we prove a refinement of the well-known Chomsky—Schützenberger Theorem, and also prove that the decision procedure for parenthesis grammars can be extended to a broader class of CF grammars.