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.

|cite|improve this question
$\endgroup$
  • 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 '12 at 19:18
  • $\begingroup$ @Patrick87. thanks. u mean L is CFG only? am i right? $\endgroup$ – user1771809 Nov 27 '12 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 '12 at 20:27
  • $\begingroup$ @user1771809 Yes, $L$ is context-free, so there is a CFG which generates it. $\endgroup$ – Patrick87 Nov 27 '12 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$ – user1771809 Nov 28 '12 at 18:43
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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is proof by complementation which doesn't work in case of CFLs. Kindly correct me if i am wrong $\endgroup$ – user1771809 Dec 12 '12 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 '12 at 17:49

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.