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.