论文标题
不含糊的明确线性语法互补
Non-closure under complementation for unambiguous linear grammars
论文作者
论文摘要
本文证明了在补充中的明确线性语言家族（即由明确线性无上下文的语法定义的）家族的不关闭。确切地说，提出了一种特定的明确线性语法，并证明该语言的补充不是由任何无上下文的语法定义的。这也构成了Hibbard和Ullian的结果的另一种证据（“无上下文语言之间固有的歧义性的独立性”，J.ACM，1966年）在补充中不明式的语言的不闭合。
The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian ("The independence of inherent ambiguity from complementedness among context-free languages", J.ACM, 1966) on the non-closure of the unambiguous languages under complementation.
