Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $ [duplicate]

Question

So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ }

is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL

i even know the grammar for it but i cannot draw the PDA because :

even if we determine the middle of the string, if we push every word of w1 to the stack, then how can we compare it to w2 when we can only POP??? how is that even possible?

i mean how can i compare two strings and determine if they are the same if i can only compare the last word of first string to the first word of the second??!

also it would help me a lot to understand if you could say which of these are CFL and which are not :

$L_1 = \{ w_1 w_2 : |w_1| =|w_2| , w_1 = w_2 \} $

$L_2 = \{ w_1 w_2 : |w_1| \neq |w_2| , w_1 \neq w_2 \} $

$L_3 = \{w_1 w_2 : |w_1| \neq |w_2| , w_1 = w_2 \} $

there was a post about this but nobody answered how can we construct such a PDA? i don't want to just convert the grammar to PDA with algorithms, i want to understand how the PDA is comparing two strings?

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

Answer 1

The three languages you ask about are not very interesting:

• $L_1$ is famously not context-free; it's usually written as $\{ ww \mid w \in \Sigma^* \}$. Note that the condition $|w_1| = |w_2|$ is obsolete. Standard entry-level proof techniques work.

• $L_2 = \Sigma^+$ since every word $w$ (except $\varepsilon$) can be split into $w_1 = \varepsilon$ and $w_2 = w$; hence it's regular.

• $L_3 = \emptyset$ since the two conditions are contradictory; hence it's regular.

As you see, neither gives you any insight into $L$. The languages discussed here are more helpful in this regard.

---

As for an NPDA for $L$, the answer you link already mentions that there are algorithms to get you from a grammar to an automaton; check a proof that NPDAs and CFGs are equally powerful.

That said, an idea for constructing an automaton from scratch is the same as for the grammar, even though it's a little messier to implement. Let $w$ be the whole input word, and rename $(w_1,w_2)$ to $(u,v)$ to avoid syntax overload. Then:

• Note that if $u \neq v$ with $|u| = |v|$, there must be $i$ so that $u_i \neq v_i$. And, importantly, if there is no such $i$ if $u=v$.
• Non-deterministically guess two input indices $j, l$ to compare.
• Non-deterministicaly guess the middle index $k$ of the input.
• Use states to verify that $w_j \neq w_l$.
• Use states to verify that $|w|$ is even.
• Use the stack to verify that $k = |w|/2$.
• Use the stack to verify that $j = l - k$.
• Reject if any of the verifications fail.

The main trick left is how to use the stack for the two checks at once; I'll leave that as an exercise. Proving that the resulting automaton does indeed accept the language is instructive about the nature of non-determinism.