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?
$\begingroup$
$\endgroup$
2
-
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$– RaphaelCommented Aug 11, 2014 at 21:01
-
$\begingroup$ Then you are already 95% of the way there. $\endgroup$– RaphaelCommented Aug 11, 2014 at 21:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
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$$
-
$\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$ Commented Aug 11, 2014 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$ Commented Aug 11, 2014 at 22:05
-
1$\begingroup$ Okay -- now prove correctness. (If there is a mistake, you'll find it during the proof attempt.) $\endgroup$– RaphaelCommented Aug 11, 2014 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$– RaphaelCommented Aug 12, 2014 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$ Commented Aug 12, 2014 at 14:47