patternMinor
unambiguous context-free languages and complementation
Viewed 0 times
freelanguagesandunambiguouscontextcomplementation
Problem
I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:
The first question above is motivated by the fact that it holds for deterministic context-free languages, which are a strict subclass of the unambiguous context-free languages.
- Is the complement of an unambiguous context-free language also a context-free language?
- If a language is context-free, and its complement is context-free as well (i.e., a so-called strongly context-free language), is it the case that the language is unambiguous context-free?
The first question above is motivated by the fact that it holds for deterministic context-free languages, which are a strict subclass of the unambiguous context-free languages.
Solution
Both questions turn out to have negative answers, as shown in [this][1] article.
In particular, the authors construct
Consequently, there is no relationship between the notion of unambiguity for context-free languages and the complementation operation.
[1] The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages" by Hibbard and Ullian, JACM, Volume 13 Issue 4, Oct. 1966, Pages 588-593
https://dl.acm.org/citation.cfm?doid=321356.321366
In particular, the authors construct
- An unambiguous context-free language whose complement is not context-free.
- An inherently ambiguous (i.e., non-unambiguous) context-free language whose complement is context-free.
Consequently, there is no relationship between the notion of unambiguity for context-free languages and the complementation operation.
[1] The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages" by Hibbard and Ullian, JACM, Volume 13 Issue 4, Oct. 1966, Pages 588-593
https://dl.acm.org/citation.cfm?doid=321356.321366
Context
StackExchange Computer Science Q#98849, answer score: 4
Revisions (0)
No revisions yet.