NTS Languages Are Deterministic and Congruential
NTS Languages Are Deterministic and Congruential
复制标题
NTS 语言是确定性且一致的
DOI：
10.1016/0022-0000(85)90056-x
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
Géraud Sénizergues
中科院分区：
文献类型：
--
作者：
L. Boasson;Géraud Sénizergues
当规则在两种情况下使用时，如果一个上下文无关文法生成的句子形式集不变，则该文法称为NTS。我们在这里证明了这种文法生成的确定性语言是同余类的有限并。此外，我们还证明了该语言族在反转和与正则集相交的情况下是闭的。即将发表的一篇论文将证明，对于这一类，等价问题是可判定的。
A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove here that such grammars generate deterministic languages which are finite unions of congruence classes. Moreover, we show that this family of languages is closed under reversal and intersection with regular sets. A forthcoming paper will prove that, for this class, the equivalence problem is decidable.