1
$\begingroup$

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'.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – ttnick
    Jan 31 at 16:57

1 Answer 1

1
$\begingroup$

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 :]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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