# Constructing a PDA for $L=${$\exists i,k\in \mathbb{N} : |w|=2k, w_i \neq w_{k+i}$}

I have the main idea, yet I'm uncertain on how to construct this PDA (in terms of states, transitions)

We can assume the alphabet $$\Sigma$$ is {$$0,1$$}, proving for $$\Sigma=$${$$0,1$$} is a sufficient proof that 'covers' all $$\Sigma$$'s such that $$|\Sigma|\geq 2$$.

I want to use the fact that the language $$L=$${$$w\in\Sigma^* : w=u_1\circ u_2 , |u_1|=|u_2| , u_1\neq u_2$$} can be constructed using a PDA, and that since $$u_1\neq u_2$$ there must be atleast one character which is in one sub-word, and isnt in the other.

Edit:

After some playing around, I've constructed 2 PDAs which I believe one might be correct, however I'm not sure how to 'test' them. The PDAs are as such: And: Edit 2:

I've managed to construct this PDA (lets call it PDA3): I feel like PDA3 is the right answer, simply because I've tried some examples and all seem to work/fail according to $$L$$, yet I have no way of formally proving it.

Is there a method to proving? except for experimenting with specific examples.