Search

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", JACM , 1966) on the non-closure of the unambiguous languages under complementation. [ABSTRACT FROM AUTHOR]

Abstract: Boolean grammars are an extension of context-free grammars, in which conjunction and negation may be explicitly used in the rules. In this paper, the notion of ambiguity in Boolean grammars is defined. It is shown that the known transformation of a Boolean grammar to the binary normal form preserves unambiguity, and that every unambiguous Boolean language can be parsed in time O(n 2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open. [Copyright &y& Elsevier]