PDA Stack
Given the following pushdown automata and input string 00001111, what does the PDA's stack look like once it has gotten through and read the second 1 of the string (i.e. the substring 000011 has been read)?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Relevant wiki: Pushdown Automata
We start off by pushing the $ symbol and then we read four 0's, and with each 0 we read, we push a 0 to the stack. Once we've read all the zeroes, there will be four 0's on the stack. Then we start reading 1's and for each 1, if there is a 0 on top of the stack, remove it. Since we will have read two 1's at this point, there will be two of the 0's from the stack removed, leaving $00 on the stack.