0
$\begingroup$

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: PDA 1

And:

enter image description here

Edit 2:

I've managed to construct this PDA (lets call it PDA3): enter image description here

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.

Improve this question
$\endgroup$
1

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.