PDA misadventures [Solved!]
Yesterday I had a final exam in a formal languages and automata course. I got through most of it okay, but got stuck on a PDA (pushdown automaton). The problem:
Design a PDA over language {a,b} such that count(a) = (2 * count(b)) + 1.
Only one stack allowed.
I stared at it for well over an hour, nearly twice as long as the rest of the test combined (tracing SLR(0) processing is fun!). Ultimately, as time was running out, and I hadn't come up with a solution, I went with something that at least solved several of the test strings that ruled out at least 6-8 other failed solutions.
I *think* this "two pops are better than one" strategy doesn't work on strings that are mixed up a lot. Like, "abaa" leaves an empty stack when input exhausts, which will be rejected.
Lazyweb corraboration/rejection of the hunch that this is wrong would be *greatly* welcome. The dot source is attached in case anybody wants to suggest a correction.
[Update (2006-05-17)] Tony's correct version, described in his comment below, looks like this:
Tweaked dotfile attached, too.
Trackback URL for this post:
| Attachment | Size |
|---|---|
| pda-from-final.dot.txt | 1.04 KB |
| pda2.dot.txt | 1.14 KB |
Tony (not verified) on May 17th 2006
Hi Dan,
This is very similar to what I did. The only difference I can see is that on the right side, after READ b, POP a, then:
POP b: push 2 b's.
POP N: push 1 b.
(it's No. 6 from homework #9, but with the middle of No. 5).
As far as I can tell, this works.
Nice blog you have here ... I will take a look at it when I get a chance.
Tony
dchud on May 17th 2006
...so I'm just pushing too many b's after the first pop, that fixes the abaa problem for sure.
I tweaked the dot file with this change and am adding it in as an update.
Thanks Tony!
Brian (not verified) on May 19th 2006
Hi Dan,
I would have replied sooner but I got really sick the day after the final and everything else happens - of course.
There was a homework problem that was similar to this test question. Before the test I actually went over this problem with our instructor. The reason was she had marked it wrong and I thought it was right. She couldn't find anything wrong with it so I used it on the exam.
I think I approached the problem as if I were writing a while loop. I first put an a or two b's on the stack and then did another read. This is the read that I came back to after all of the popping and pushing. At first I thought that my popping and pushing scheme was different than the one above but after a close look it appears to be the same. What I forgot to do on the test is that one last pop after the final a to make sure nothing was left on the stack. SIGH.
Most likely this is the last conversation about PDAs that I will ever have. CHEERS.
Have a great summer.
Brian
Post new comment