patternMinor
Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free?
Viewed 0 times
thefreewxwlanguagecontextcomplement
Problem
I know that the Context-free languages are not closed under compliment.
Given $L=\{wxw^r| w \in(a+b)^+,x \in (a+b)\}$ and this is a Context free language. I think it's compliment will contain words of the form $ww$ which comes under CSL.So, I think this $\lnot L$ must be not context-free.But I've read here
Why are palindrome and not-palindrome both context-free?
that palindromes are closed under complement.
Can someone please guide over this?
Given $L=\{wxw^r| w \in(a+b)^+,x \in (a+b)\}$ and this is a Context free language. I think it's compliment will contain words of the form $ww$ which comes under CSL.So, I think this $\lnot L$ must be not context-free.But I've read here
Why are palindrome and not-palindrome both context-free?
that palindromes are closed under complement.
Can someone please guide over this?
Solution
Generally speaking, the way to figure out whether a given language is context-free is twofold:
If any of these methods succeed, you will have found whether the language is context-free.
In your particular case, we can notice that a word $y$ is not in $L$ if one of the following three cases occurs:
In the third case, let us suppose that $z_i = \alpha \neq \beta = (w^R)_i$, and put $\ell = |z| = |w|$. Then $y \in \Sigma^{i-1} \alpha \Sigma^{\ell-i} \sigma \Sigma^{\ell-i} \beta \sigma^{i-1}$, and all such words are not in $L$. We conclude that
$$
\overline{L} = (\Sigma\Sigma)^* \cup \Sigma \cup \bigcup_{\substack \sigma, \alpha \neq \beta \in \Sigma \\ j,k \geq 0} \Sigma^j \alpha \Sigma^k \sigma \Sigma^k \beta \Sigma^j.
$$
It is routine to construct a context-free grammar for the expression on the right, and so $\overline{L}$ is context-free.
- Try proving that it is not context-free, say using the pumping lemma.
- Try proving that it is context-free, say by constructing a grammar or a PDA.
If any of these methods succeed, you will have found whether the language is context-free.
In your particular case, we can notice that a word $y$ is not in $L$ if one of the following three cases occurs:
- $y$ has even length.
- $y$ has length one.
- $y$ has odd length, and when written as $y = z \sigma w^R$, with $|z| = |w|$, the two words are different.
In the third case, let us suppose that $z_i = \alpha \neq \beta = (w^R)_i$, and put $\ell = |z| = |w|$. Then $y \in \Sigma^{i-1} \alpha \Sigma^{\ell-i} \sigma \Sigma^{\ell-i} \beta \sigma^{i-1}$, and all such words are not in $L$. We conclude that
$$
\overline{L} = (\Sigma\Sigma)^* \cup \Sigma \cup \bigcup_{\substack \sigma, \alpha \neq \beta \in \Sigma \\ j,k \geq 0} \Sigma^j \alpha \Sigma^k \sigma \Sigma^k \beta \Sigma^j.
$$
It is routine to construct a context-free grammar for the expression on the right, and so $\overline{L}$ is context-free.
Context
StackExchange Computer Science Q#98320, answer score: 2
Revisions (0)
No revisions yet.