0
$\begingroup$

Identify the language given by $L = \{ x \in (0,1)^* : x \neq ww^R, w \in (0,1)^*\}$. Note: $w^R$ is the reverse of the string $w$.

Closure property can/should be applied only in the cases when the actual language is not specified. Otherwise, you may arrive at wrong conclusions. The language in question is fully specified, so I doubt whether one can directly apply closure property on $ww^R$, which you say, is its complement or vice versa. The given answer is CFL. But I don't seem to have arrived at it satisfactorily.

$\endgroup$
6
  • 4
    $\begingroup$ What kind of answer are you looking for? The language given is the complement of the language of all even-length palindromes over $\{0, 1\}$. The complement over the universe $\{0, 1\}^*$ is the language of all odd-length words and even-length non-palindromes. If you want a CFG, first make one for odd-length words, then for non-palindromes, and take the union. $\endgroup$
    – Patrick87
    Nov 27, 2012 at 19:18
  • $\begingroup$ @Patrick87. thanks. u mean L is CFG only? am i right? $\endgroup$ Nov 27, 2012 at 19:26
  • 3
    $\begingroup$ What are you asking for? The language $L$ is context-free, and so is its complement. However, you cannot apply closure properties, since CFL are not closed under complement. Do you need a proof that $L$ is context-free? $\endgroup$
    – A.Schulz
    Nov 27, 2012 at 20:27
  • $\begingroup$ @user1771809 Yes, $L$ is context-free, so there is a CFG which generates it. $\endgroup$
    – Patrick87
    Nov 27, 2012 at 20:54
  • $\begingroup$ @A.Schulz yes i am looking for a proof. i get confused when i saw a complement of CFG as CFG itself. $\endgroup$ Nov 28, 2012 at 18:43

1 Answer 1

2
$\begingroup$

If you want to show that $L$ is context-free, you can proceed as follows:

Build a push-down automaton $P$ that accepts $L$. $P$ will read the input and put all the read characters on its stack. At some point it guesses (non-deterministically!) that half of the input has been read. Then it reads the remaining input and checks it a against its stack. If $P$ finds a mismatching character it accepts, if it does find not a mismatch, or the guess for the middle of the word was wrong, it rejects.

$\endgroup$
2
  • $\begingroup$ This is proof by complementation which doesn't work in case of CFLs. Kindly correct me if i am wrong $\endgroup$ Dec 12, 2012 at 17:41
  • $\begingroup$ No it is not using "complementation". The PDA I sketched accepts $L$ not $\bar L$. Maybe the non-determinism confuses you. The PDA accepts, if there exists at least one accepting run. So you can "guess", when half of the input has been read. If your guess was wrong you reject. But there is one correct guess, if $x\in L$. $\endgroup$
    – A.Schulz
    Dec 12, 2012 at 17:49

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.