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
    Commented Nov 19, 2018 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
    Commented Nov 19, 2018 at 18:14

1 Answer 1


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 and acknowledge you have read our privacy policy.

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