HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

unambiguous context-free languages and complementation

Submitted by: @import:stackexchange-cs··
0
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:

  • 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

  • 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.