4
$\begingroup$

I am initiating myself into TOC and using sort of random resources from the web. I was looking at this problem from a Berkeley problem set: Construct a PDA to accept $ L = {a^ib^j|i \neq j , 2i \neq j} $ And I don't understand the given solution here.(Problem 4) http://www.cs.berkeley.edu/~isabelle/cs302/ps3-solutions.pdf

When can we say this machine accepts a string? From my understanding, it seems to accept ab,aabb,aaabbb etc as well when it shouldn't.

1 Answers 1

1

There are multiple different definitions of push-down automata that differ in the details of the acceptance condition. One common condition that is (presumably) in use here is that a word is accepted if:

  1. The push-down automaton arrives in an accepting state,
  2. The stack is empty.

If you follow the behaviour of the automaton in the answer, you will find that for words $a^ib^i$ or $a^ib^{2i}$, if you arrive in a final state, the stack will not be empty, so the word is not accepted.