Grammars Without Erasing Rules - The OI Case
Grammars Without Erasing Rules - The OI Case
复制标题
不删除规则的语法 - OI 案例
DOI：
10.1007/3-540-10828-9_68
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
B. Leguy
中科院分区：
文献类型：
--
作者：
B. Leguy
本文将上下文无关语言中的ε-规则问题推广到树的情形。对于上下文无关树文法，我们区分三类擦除规则：不完全规则，ε-规则和一元ε-规则（即X（x2）→x1）。对于擦除规则仅为第三类的文法，可以得到免擦除文法，并提供了一个构造。其他结果是负面的，我们证明，一般擦除规则是无法避免的。
The problem of ε-rules in context-free languages is generalized to the tree-case. For context-free tree grammars, we distinguish three classes of erasing rules : incomplete rules, ε-rules and monadic ε-rules (i.e. rules like X(x2)→x1). For grammars with erasing rules of just the third class, erasing-free grammars can be obtained and a construction is provided. Other results are negative and we prove that generally erasing rules cannot be avoided.