0
$\begingroup$

I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf

I found question 3g to construct a pushdown automata for the following:

{$ {a^i b^j}$ | ${i \neq j}$}

The solution they provided is below:

PDA Solution

The issue is, when I use JFLAP to test out, I get aabb to pass - when it should just be aabbb, aaabb, etc.

I looked around, and found another solution that also failed:

Solution 2

Can someone explain to me why these fail on JFLAP and if they are right or wrong? The PDA I'm looking for can accept even if there are objects on the stack. Perhaps these two rely on the fact that acceptance is only reached if there is nothing on the stack?

$\endgroup$
1
$\begingroup$

The intuition is push the number of $a$'s then pop while reading $b$'s. The result should be non-zero: either there are still items on the stack (which we can check), or the stack has been emptied before the end of the string.

There is a problem with instructions like "$b/\varepsilon/\varepsilon$". This instruction means "read $b$ and do not push nor pop". The middle $\varepsilon$ is misleading. It does not mean that the stack is empty. It just means the PDA does not look at it.

The solution is to start by pushing a nice bottom-of-stack symbol $Z$ at the start of the computation. When we see a $Z$ we know the bottom has been reached.

$\endgroup$
  • $\begingroup$ I believe the Z is there by default (at the bottom of the stack). I tried something out and put it in as an edit. It works in JFLAP but do you think there's something wrong with it? $\endgroup$ – Andrew Raleigh Jan 28 at 19:12
  • $\begingroup$ Well, if the $Z$ is there by default, that is OK, but it should be tested to verify the moment where the number of $a$'s equals the number of $b$'s. $\endgroup$ – Hendrik Jan Jan 28 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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