[Solved]: PDA recognising all strings with a $1$ in the second half

ignougroup
Problem Detail: My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says:

Let $Sigma = {0,1}$ and $B$ is the collection of all strings that contain at least one $1$ in the second half. To state it more precisely: $B={uvmid u in Sigma^{ast}, v in Sigma^{ast} 1 Sigma^{ast}, |u|geq|v|}$. Give a PDA that recognizes $B$. Give a diagram to describe your PDA.

My question is why do I need a PDA or really a stack for this because all I am looking at is the second half which I can just epsilon to the second half and then when I read a $1$, go to the accept state. For example if $u=1001010101$ and $v=000011$, wouldnt I just loop around for a bit for u and then epsilon over to say I am now looking at $v$. Then when I read the first $1$, I just accept. I wouldnt need to use the stack at all would I? I’m not sure if I understand it correctly or not and would appreciate any help.

Asked By : user1715916

Answered By : Luke Mathieson

The problem with your approach is that you are not checking that $|u| geq |v|$ – for example the string $0100$ would be accepted. Remember that the ‘magic’ of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to. So in this case, you still need to check that the size of the two parts are suitable, for which we need1 a stack. As a side note, $B$ can also be expressed as ${u1vmid u in Sigma^{ast}, v in {0}^{ast}, |u| geq |v|}$, not that this really changes much, but it’s a little simpler (in terms of the PDA). Footnotes:

  1. As Babou points out in his answer, you don’t need a stack as such, a simple counter suffices, but you do need something beyond what a DFA/NFA can manage.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35166