# Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$

Problem Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$

For the language $wcw^R$, it's much easier because the stack is always empty after matching one character from left and one character on the right. Otherwise, it will reject if there is no transition out of a current state.
The language above, however, there are several cases after $c$ is read. Here is my attempt,

Consider the case when $w_1 = w_2^R$, one example of this case would be: $abcba$. Otherwise,it will falls into these three cases:

• $|w_1| > |w_2|$.
• $|w_1| < |w_2|$.
• $|w_1| = |w_2|$ but doesn't satisfy the property $w_1 = w_2^R$. For example $abcab$ or $abcaa$.

Let's take a look at case 1, $|w_1| > |w_2|$. The scratch algorithm is as follows:

• At stage 0, If we read an $a$, push a $x$ onto stack
• At stage 0, If we read a $b$, push a $y$ onto stack
• At stage 0, If we read a $c$, push nothing, pop nothing, goes to stage 1
• At stage 1, If we read an $a$ and top of the stack is $x$, pop $x$
• At stage 1, If we read an $a$ and top of the stack is $y$, do nothing
• At stage 1, If we read an $b$ and top of the stack is $y$, pop $y$
• At stage 1, If we read an $b$ and top of the stack is $x$, do nothing

and because $|w_1| > |w_2|$, then after stage 1 our stack is never empty we will be at the end of input. In short, unless the stack is empty and there are no other inputs to read, we're ready to accept input.

So my question is, does my PDA look reasonable? I'm a little confused when defining the transition state which handles empty stack with more input and non-empty stack with no more input. Any suggestion on improvement would be greatly appreciated. Thank you.

-
If you know how to accept $w_1 c w_1^R$ then all you need to do is accept the intersection of $\{a,b\}*c\{a,b\}*$ (regular) with $\text{not} (w_1 c w_1^R)$. –  Peter Taylor Aug 25 '11 at 9:01
This question would have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! –  Raphael Dec 15 '11 at 13:48

First, I think that in Linz’s solution $\Gamma$ should be $\{x,y\}$, not $\{x,\phi\}$: he clearly needs $y$ to be in $\Gamma$, and judging from his PDA, $\phi$ is his symbol for an empty stack. That’s why at $q_0$ he has $a,\phi\to x\phi$ as well as $a,x\to xx$ and $a,y\to xy$: when $a$ is read, he needs the PDA to push $x$ onto the stack no matter whether the stack is empty, has $x$ on top, or has $y$ on top. (Similarly for the three $b$ instructions.) His loop at $q_0$ and transition to $q_1$ correspond to the first three bullet items in your scratch algorithm. His loop at $q_1$ corresponds to the rest of your bullet points.

If the input runs out before the stack is emptied, he pops one symbol off the stack and goes to $q_2$: $\epsilon,x\to\epsilon;\epsilon,y\to\epsilon$. If the stack is emptied while there is still input, he simply goes to $q_2$: $a,\epsilon\to\epsilon;b,\epsilon\to\epsilon$. Thus, if the input and stack are exhausted at the same time, the PDA halts at $q_1$. It’s not hard to see that this happens iff $|w_1| = |w_2|$ and every letter of $w_2$ caused a letter to be popped off the stack, i.e., iff $w_2 = w_1^R$. Thus, the PDA fails to accept any word of the form $wcw^R$ with $w \in \{a,b\}^*$.

Any other input will eventually send the PDA to $q_2$. The top two instructions in the loop at $q_2$ apply when the input runs out before the stack is emptied and serve to empty the stack. The other two apply when the stack is emptied while there is still input and serve to exhaust the input. When the input is exhausted and the stack is empty, the PDA goes to $q_3$ and halts, accepting the input. This clearly works.

I don’t understand the first transition in the other PDA ($\epsilon,\epsilon\to\phi$); I have a suspicion that you’ve misunderstood Linz’s use of $\phi$, but you’re also using a notation that I don’t entirely understand.

An alternative approach would be to start with the loop at $q_0$ and transition to $q_1$ exactly as in Linz’s PDA. Loop at $q_1$ with $a,x\to\epsilon;b,y\to\epsilon$, and add $a,y\to\epsilon$ and $b,x\to\epsilon$ to the transition from $q_1$ to $q_2$. Now loop at $q_2$ until input and stack are both exhausted; this requires the additional instructions $a,x\to\epsilon;a,y\to\epsilon;b,x\to\epsilon;$ and $b,y\to\epsilon$, besides the four that are already there. Leave $q_3$ and the transition from $q_2$ to $q_3$ as they are. This PDA transfers from $q_1$ to $q_2$ the moment $w_2$ deviates from $w_1^R$ in any way, either by having a wrong letter or by having the wrong length; if this never happens, the input and stack are exhausted simultaneously while the PDA is still in state $q_1$, and the PDA is stuck there in a non-accepting state.

-
First, thanks a lot for your a very detailed answer. Sorry for confusing you when putting in the name of two authors. They are all my own solution, I put their name there just to distinguish between two different types of notation used. Besides, the notation $\varepsilon, \varepsilon \rightarrow \phi$ means push the initial stack symbol $\phi$ on the stack first, because according to Micheal Sipser, his PDA is only a 6-tuples instead of 7. In Linz's way, his stack already contains the stack symbol $\phi$. $\phi$ is my own notation for stack symbol because I think it catch my eyes better. –  Chan Aug 26 '11 at 1:50
(cont.) Linz uses $Z$ and Sipser use \\$. On the other hand, the solution above was wrong because PDA is way smarter than I initially thought, by that I meant it will process using brute force algorithm to determine if a string is in the language. Since it's a long to explain what was going on in my above solution, I will write it down as a complete answer. Once again, many thanks for your time reading. –  Chan Aug 26 '11 at 1:53