# Not understanding example of a Pushdown Automata

The first example of a (nondeterministic) pushdown automata given in Linz' An Introduction to Formal Languages and Automata is the following:

Example 7.2: consider

• $$Q = \{q_0,q_1,q_2,q_3\}$$,
• $$\Sigma = \{a,b\}$$,
• $$\Gamma = \{0,1\}$$,
• $$z = 0$$,
• $$F = \{q_3\}$$,

with $$q_0$$ the initial state and

• $$\delta (q_0,a,0) = \{(q_1,10),(q_3,\lambda)\}$$,
• $$\delta (q_0,\lambda,0) = \{(q_3,\lambda)\}$$,
• $$\delta (q_1,a,1) = \{(q_1,11)\}$$,
• $$\delta (q_1,b,1) = \{(q_2,\lambda)\}$$,
• $$\delta (q_2,b,1) = \{(q_2,\lambda)\}$$,
• $$\delta (q_2,\lambda,0) = \{(q_3,\lambda)\}$$.

The author states

The crucial transitions are $$δ (q_1, a, 1) = \{(q_1, 11)\},$$ which adds a $$1$$ to the stack when an $$a$$ is read, and $$δ (q_2, b, 1) = \{(q_2, λ)\},$$ which removes a $$1$$ when a $$b$$ is encountered. These two steps count the number of $$a$$’s and match that count against the number of $$b$$’s.

How does the automata count the number of $$a$$'s and $$b$$'s?

What exactly does the transition $$δ (q_1, a, 1) = \{(q_1, 11)\}$$ do to the stack? If the transition is crucial in counting the $$a$$'s, then I'd imagine it 'enqueues' another $$1$$ into the stack e.g. the stack goes from $$110...$$ to $$1110...$$

However, I fail to see how the formal definition of the pushdown automata would keep track of the stack, as we are only given the stack alphabet $$\Gamma$$ and the stack starting symbol $$z$$, so the information regarding what the stack contains at each point in time is not 'saved'.

• I am not sure if I understand the question. There is a finite set of control states $Q$ (which can actually be eliminated without losing the expressive power of a PDA) and a stack. Both together yield a state or configuration $(q, \gamma)$, where $\gamma \in \Gamma^\ast$ is the stack content. Every transition involves reading the next symbol of the input (or $\lambda$ / $\varepsilon$) and the top of the stack and replacing control state by a different state and the top of the stack by a word. Jan 31 at 16:57

the stack is kept track of by a so called "configuration". Imagine, that the configuration represents a complete description of your machine at a point in time. The transition function only needs to tell you, how the configuration might change during the computation.

For a PDA $$A = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$$, a config needs to keep track of the current state, remaining input, and stack. So a config is a 3-tuple $$(q, u, v)$$ where $$q \in Q$$ is a state, $$u \in \Sigma^*$$ is the remaining input and $$v \in \Gamma^*$$ is the stack. Now $$\delta(q, a, v) \ni (q', v')$$ can be read as "if in state $$q$$ you read $$a$$ and your stack top is $$v$$, you might change to state $$q'$$ by popping $$v$$ and pushing $$v'$$". Using our configs we can write $$(q, au, vs) \vdash (q', u, v's) \iff \delta(q, a, v) \ni (q', v')$$ where $$C \vdash C'$$ represents one step in the computation, the machine changes from $$C$$ to $$C'$$ in one step. So a computation for $$aaabbb$$ in your example machine might look something like this:

• $$(q_0, aaabbb, 0) \vdash (q_1, aabbb, 10)$$
• $$(q_1, aabbb, 10) \vdash (q_1, abbb, 110)$$
• $$(q_1, abbb, 110) \vdash (q_1, bbb, 1110)$$
• $$(q_1, bbb, 1110) \vdash (q_2, bb, 110)$$
• $$(q_2, bb, 110) \vdash (q_2, b, 10)$$
• $$(q_2, b, 10) \vdash (q_2, \lambda, 0)$$
• $$(q_2, \lambda, 0) \vdash (q_3, \lambda, \lambda)$$

We say that the PDA accepts $$w \in \Sigma^*$$ iff $$(q_0, w, z) \vdash^* (q_f, \lambda, \lambda)$$ and $$q_f \in F$$, so your PDA accepts $$aaabbb$$.

Hope that helps :]