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.
 A: 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.
