patternMinor
Deciding whether complement of context-free language is context-free
Viewed 0 times
freelanguagecontextdecidingcomplementwhether
Problem
I need to find out if the following problem is decidable:
Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language.
I am having trouble in defining the $TM$ I need in order to solve this problem. My thinking was to see if it is possible to construct a $TM$ that takes an encoding of a $CFL$ as input and halts in an accept or reject state depending on whether $\bar{L}$ is a $CFL$ or not. Is this line of thinking correct? If so, may I also know how to proceed further.
Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language.
I am having trouble in defining the $TM$ I need in order to solve this problem. My thinking was to see if it is possible to construct a $TM$ that takes an encoding of a $CFL$ as input and halts in an accept or reject state depending on whether $\bar{L}$ is a $CFL$ or not. Is this line of thinking correct? If so, may I also know how to proceed further.
Solution
Your problem can be formalized in several equivalent ways:
-
Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^* \setminus L(G)$ context-free?
-
Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free?
Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We stick to the first one.
It is well-known that given a context-free grammar $H$ over $\Sigma$, deciding whether $L(H) = \Sigma^*$ is undecidable. We will reduce this problem to Problem 1.
Let us be given a context-free grammar $H$ over $\Sigma$. If $\Sigma$ is a singleton, then $L(H)$ is regular, and so $\Sigma^* \setminus L(H)$ is also regular and context-free. Otherwise, let $a,b \in \Sigma$ be two distinct symbols. Construct a grammar $G$ over $\Sigma \cup \{\#\}$ (where $\#$ is a fresh symbol) for the language
$$
L = (\Sigma^ \setminus \{ww : w \in \Sigma^\}) \# \Sigma^ \cup \Sigma^ \# L(H).
$$
If $L(H) = \Sigma^$ then $L = \Sigma^ \# \Sigma^*$ is regular, and so its complement is regular and context-free. Otherwise, let $x \notin L(H)$. If $\overline{L}$ were context-free, then so would the following language be:
$$
\overline{L} \cap \Sigma^ \# x = \{ww : w \in \Sigma^\} \# x.
$$
This would imply, however, that $\{ww : w \in \Sigma^*\}$ is context-free, which is known to be false.
Summarizing, $\overline{L(G)}$ is context-free iff $L(H) = \Sigma^*$.
Compare Theorems 11–12 in Hendrik Jan's notes.
-
Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^* \setminus L(G)$ context-free?
-
Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free?
Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We stick to the first one.
It is well-known that given a context-free grammar $H$ over $\Sigma$, deciding whether $L(H) = \Sigma^*$ is undecidable. We will reduce this problem to Problem 1.
Let us be given a context-free grammar $H$ over $\Sigma$. If $\Sigma$ is a singleton, then $L(H)$ is regular, and so $\Sigma^* \setminus L(H)$ is also regular and context-free. Otherwise, let $a,b \in \Sigma$ be two distinct symbols. Construct a grammar $G$ over $\Sigma \cup \{\#\}$ (where $\#$ is a fresh symbol) for the language
$$
L = (\Sigma^ \setminus \{ww : w \in \Sigma^\}) \# \Sigma^ \cup \Sigma^ \# L(H).
$$
If $L(H) = \Sigma^$ then $L = \Sigma^ \# \Sigma^*$ is regular, and so its complement is regular and context-free. Otherwise, let $x \notin L(H)$. If $\overline{L}$ were context-free, then so would the following language be:
$$
\overline{L} \cap \Sigma^ \# x = \{ww : w \in \Sigma^\} \# x.
$$
This would imply, however, that $\{ww : w \in \Sigma^*\}$ is context-free, which is known to be false.
Summarizing, $\overline{L(G)}$ is context-free iff $L(H) = \Sigma^*$.
Compare Theorems 11–12 in Hendrik Jan's notes.
Context
StackExchange Computer Science Q#132411, answer score: 6
Revisions (0)
No revisions yet.