# PDA recognising all strings with a $1$ in the second half

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=\{uv\mid 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.

• I criticized (unfairly) Luke Mathieson's answer. Actually, it is your instructor who seems to have been inconsistent, if you were faithful to his statement of the problem. There is no such thing as half a string of odd length. So his definition should exclude odd length, or avoid talking of half a string. – babou Dec 12 '14 at 10:35
• See here for how to show that the language is not regular. Of course there are other machine models that can accept $B$, but in the "usual" hierarchy you'll need at least PDA. – Raphael Dec 12 '14 at 11:30
• @Raphael Yes, in the usual hierarchy, its a PDA. But I think it is always nice to open a bit onto other things when there is an opportunity. Many of the problems addressed here are actually counter problems, which also means much simpler than PDA problems. – babou Dec 12 '14 at 12:18
• @babou What is an example of a language that can be recognised with a stack but not with a counter? Note that by Chomsky-Schützenberger, CFL are essentially (i.e. the part not dealt with by the finite control) Dyck languages. Balancedness can be checked with one counter per type of parentheses, and a finite set of counters can be simulated with one counter. This may depend on what you are allowed to do with your counter. – Raphael Dec 12 '14 at 18:22
• @Raphael The simplest example, I think is D2, the Dyck language of balanced strings on two pairs of parentheses. The grammar is $S\to SS\mid(S)\mid[S]\mid\epsilon$. – babou Dec 12 '14 at 21:03

## 2 Answers

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 $\{u1v\mid 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.
• I forgot about checking to see if u was greater or equal to v. Thank you and God bless. – user1715916 Dec 12 '14 at 1:25
• Sorry I have one more small question related to this problem. What would I do if there is no input to be read left? Assuming u is greater than v, the input would run out before the stack has been emptied. – user1715916 Dec 12 '14 at 1:55
• @user1715916, there's two ways of looking at it. The one I'd go with (entirely because of the way I was originally taught) is that you don't need an empty stack to accept, so running out of input with stuff still on the stack is actually what you want. The second, if you want an empty stack before you accept, is to just unwind the stack when in the state that's dealing with the ending $\Sigma^{\ast}$ substring (add a self loop transition reading nothing from the input, popping anything off the stack and pushing nothing). – Luke Mathieson Dec 12 '14 at 3:02
• There are more states before this but I have it to where once it reads a 1 in the second half, it goes to a state q1. At that q1 if it reads 0 or 1 and there is nothing on the stack, it goes to q2 that just loops because that would mean v is greater than u which cant happen. If at q1 I have epsilon,$->epsilon which goes to an accept state which means that u=v. Now how would I show that u>=v? I can't keep poping the stack but if I run out of input I am not yet at an accept state. – user1715916 Dec 12 '14 at 4:14 • @user1715916, you can have a transition from$q_{1}$to itself that is$\varepsilon, \Sigma \rightarrow \varepsilon$that just unwinds any extra stuff on the stack, then move to the accept state. If you want to have a pure empty stack acceptance state, you need a nondeterministic jump when processing$u$that decides when to stop counting (i.e. when you've seen enough to match up$v$, but then don't care about the rest of$u\$). Note that for nondeterministic PDAs, requiring and empty stack as an acceptance condition and requiring no more input are equivalent. – Luke Mathieson Dec 12 '14 at 4:45

You do not need a stack to do this, but you do need a counter. A counter automaton is a PDA with only a single stack symbol (there may be a second one used only to mark the bottom of the stack, and thus test emptyness). It is a strictly weaker type of automaton.

This is needed to identify the first half of your string that you want to epsilon away.

Then, non-determinism is your friend. You read the first half of the string, and epsilon it away, as you say. But you are careful to count the length of the first half in your counter/pushdown.

They you read the second half checking it contains a 1, but also decrementing the counter to check that the "second half" has the same length as the first. If both conditions are met, you accept, else you reject.

Non-determinism is used only to decide when you have reached the middle of the string. If you do the wrong choice, your computation fails. But if the string is in the language and you do the right choice, then the compuation succeeds ... which is all you want.

• I reused your expression "to epsilon as string" but it is a bit strange. – babou Dec 12 '14 at 10:19
• Well, a counter is just a stack, isn't it? – Raphael Dec 12 '14 at 11:29
• @Raphael not quite. It is easily implemented with a stack using a single symbol. But it is strictly less powerful than a PDA. Actually, you can make a theory of counter languages that mimic that of CF languages. I think it even has its own Chomsky-Schutzenberger theorem, but based on D1, the Dyck language with only one kind of parenthesis. – babou Dec 12 '14 at 12:14
• I'd have to look up the details, but two-counter machines are Turing-complete and the proof I seem to remember goes like this: "Use the counters to simulate a stack each. Two-stack automata are Turing-complete." Ergo, one counter equals one stack? – Raphael Dec 12 '14 at 18:17
• @Raphael No! One counter is strictly less than a stack. But two counters can represent two stacks (with some affort). If you want to know how, I know about this site that answers questions in return for "reputation". – Hendrik Jan Dec 12 '14 at 20:01