Skip to main content
1 of 4

Push Down Automata Confusion with Problem

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={u,v|u is an element of sigma^, v is an element of sigma^ 1 sigma^* and |u|>=|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.