-2
$\begingroup$

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language.

Can anyone help me produce a PDA or give me any hint how I can quickly understand why this is context-free?

$\endgroup$
  • 1
    $\begingroup$ What have you tried and where did you get stuck? Can you construct a PDA for the set of (equal-length) palindromes? $\endgroup$ – Raphael Aug 11 '14 at 21:01
  • $\begingroup$ yse i can for palindrom. $\endgroup$ – user3661613 Aug 11 '14 at 21:11
  • $\begingroup$ Then you are already 95% of the way there. $\endgroup$ – Raphael Aug 11 '14 at 21:16
  • $\begingroup$ Dear @Raphael, i post a solution, would you please verify it. in fact i think this is not language of non-palindrome... $\endgroup$ – user3661613 Aug 11 '14 at 21:38
1
$\begingroup$

The language of even-length non-palindromes is given by the following context-free grammar:

$$S \rightarrow 0S0 \mid 1S1 \mid D$$ $$D \rightarrow 1A0 \mid 0A1$$ $$A \rightarrow \lambda \mid 00A \mid 01A \mid 10A \mid 11A$$

$\endgroup$
  • $\begingroup$ This answer is actually quite close to giving a grammar which generates the language in the question. The only problem with this language is that it generates some strings of odd length. This can be fixed by eliminating the rules A -> 0A and A -> 1A and adding the rules A -> 00A, A -> 01A, A -> 10A, A -> 11A. This will guarantee the generated string has even length (since all productions add an even number of terminal symbols). $\endgroup$ – Patrick87 Aug 11 '14 at 22:03
  • $\begingroup$ Intersection of two CFGs is not CF. Get rid of the second part; it's not necessary. Once you make the changes to the first grammar I specify above, you'll have a grammar for your language. To understand why, observe that: all strings will have even length; all strings will contain at least one mismatch; any even string with a mismatch can be generated by the grammar. If you have questions about one of those specifically, let me know. $\endgroup$ – Patrick87 Aug 11 '14 at 22:05
  • 1
    $\begingroup$ Okay -- now prove correctness. (If there is a mistake, you'll find it during the proof attempt.) $\endgroup$ – Raphael Aug 11 '14 at 22:20
  • 1
    $\begingroup$ @user3661613 I don't know what your learning goal is, but in some scenarios being able to write down a (maybe) correct grammar is worth nothing if you can't show it's correct. Therefore, I recommend you look into proof techniques as well; this is not too hard, i.e. something that I would comfortably expect of first-year CS undergrads in an exam (just for reference). $\endgroup$ – Raphael Aug 12 '14 at 6:09
  • 1
    $\begingroup$ @user3661613 If you understand the sketch I give in the comments, just rewrite it in your own words in the answer. If you don't understand it, tell me and I'll explain myself. I assume you do want to understand why the grammar is right, yes? That's all a proof is: an explanation of why the grammar is right. It's certainly not something you'd need to know how to do before a class on the subject or, for that matter, after a class on the subject, either. $\endgroup$ – Patrick87 Aug 12 '14 at 14:47

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.