I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:

  1. Is the complement of an unambiguous context-free language also a context-free language?
  2. 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.

  • $\begingroup$ Please ask only one question per post. The two here don't seem to be related at all are better asked separately. $\endgroup$ – Raphael Nov 19 '18 at 18:14
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 19 '18 at 18:14

Both questions turn out to have negative answers, as shown in [this][1] article. In particular, the authors construct

  1. An unambiguous context-free language whose complement is not context-free.
  2. 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.