3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – babou
    Commented Dec 12, 2014 at 10:35
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Dec 12, 2014 at 11:30
  • $\begingroup$ @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. $\endgroup$
    – babou
    Commented Dec 12, 2014 at 12:18
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Commented Dec 12, 2014 at 18:22
  • $\begingroup$ @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$. $\endgroup$
    – babou
    Commented Dec 12, 2014 at 21:03

3 Answers 3

Reset to default
3
$\begingroup$

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.
Improve this answer
$\endgroup$
11
  • $\begingroup$ I forgot about checking to see if u was greater or equal to v. Thank you and God bless. $\endgroup$
    – user1715916
    Commented Dec 12, 2014 at 1:25
  • $\begingroup$ 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. $\endgroup$
    – user1715916
    Commented Dec 12, 2014 at 1:55
  • $\begingroup$ @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). $\endgroup$
    – Luke Mathieson
    Commented Dec 12, 2014 at 3:02
  • $\begingroup$ 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. $\endgroup$
    – user1715916
    Commented Dec 12, 2014 at 4:14
  • $\begingroup$ @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. $\endgroup$
    – Luke Mathieson
    Commented Dec 12, 2014 at 4:45
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I reused your expression "to epsilon as string" but it is a bit strange. $\endgroup$
    – babou
    Commented Dec 12, 2014 at 10:19
  • $\begingroup$ Well, a counter is just a stack, isn't it? $\endgroup$
    – Raphael
    Commented Dec 12, 2014 at 11:29
  • $\begingroup$ @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. $\endgroup$
    – babou
    Commented Dec 12, 2014 at 12:14
  • $\begingroup$ 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? $\endgroup$
    – Raphael
    Commented Dec 12, 2014 at 18:17
  • $\begingroup$ @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". $\endgroup$
    – Hendrik Jan
    Commented Dec 12, 2014 at 20:01
0
$\begingroup$

Here's a sketch of a PDA which does the job:

In state $q_0$, push the symbol | (a tally marker) onto the stack and consume one input symbol, or do an epsilon transition to $q_1$.

In state $q_1$, on input $1$, pop a tally marker and transition to $q_2$. On input $0$, pop a tally marker and stay in $q_1$.

In state $q_2$, accept. For example, on any input symbol, pop a tally marker. Maybe also pop a tally marker on epsilon.

The exact behavior in $q_2$ depends on what counts as an accepting configuration in the particular definition of DFA you're working with.

I believe this deals with all even-length strings. By the precise definition given, the second half excludes the middle character in odd-length strings. To account for this, add a transition from $q_0$ to $q_1$ which consumes an input symbol without changing the stack.

Why do you need a stack? As others have pointed out, other bookkeeping structures such as a counter would suffice; in fact, I'm using the stack as a counter.

A more limited but still instructive question is then: where do I rely on the stack in my specific solution? How and why would it break if the stack was removed? (In other words: instead of asking "why does every solution need a stack?" we can ask "why does this one solution need a stack?".)

The main idea of my construction is similar to yours (OP's): twiddle my thumbs while waiting for a $1$, then go to an accepting state. Of course, a $1$ in the first half of the string (or at the middle position) shouldn't cause the PDA to accept. I use the stack-as-a-counter to know (in a non-deterministic sense) whether the input symbol being consumed is in the second half of the string or not.

Without the stack-as-counter, well, I don't know what my construction would be, but if it was coherent it probably would accept $10$ even though it shouldn't.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.