Reading
Sections 3.4 of Theory of Computing, A Gentle Introduction.
Homework
Then printout the homework and answer the questions on that paper.

Configurations
The 6-tuple (Q,Σ,Γ,Δ,s,W) tells you what a PDA is, but it doesn't tell you how the thing works ... it's kind of like having the Monopoly board and pieces without haveing the rules that tell you how to play. In the next few sections, we'll develop those rules. The first step is to define a notion of configuration.

Definition: For PDA M = (Q,Σ,Γ,Δ,s,W) a configuation of M is a 3-tuple (p,w,v) ⊆ Q × Σ* × Γ *, where p is the current state, w is the unread input, and v is the contents of the stack. Note: the bottom of the stack corresponds to the far right of the string.

Just as with finite automata, a configuration is like a snapshot of the machine in the middle of a computation. It has all the information you would need to continue the computation from that point.

Yields in One Step ($\Rightarrow$) and Zero-or-more Steps ($\Rightarrow^*$)
A machine is allowed to go from one configuration to another provided there is a transition that allows it. This means we really need to precisely define what a transition is, i.e. what does it do to a machine when it is taken. That's our good friend "yields in one step". It provides the rules for how the machine works!

Definition: For machine $M = (Q,\Sigma,\Gamma,\Delta,s,W)$, configuration $(p,u,v)$ yields $(q,u',v')$ in one step [which we write as $(p,u,v) \Rightarrow_M (q,u',v')$] provided that there is an $x \in \Sigma \cup \lambda$, and strings $r,y,z \in \Gamma^*$ such that
  1. $u = xu'$,      $\leftarrow$ means $x$ is the character read or, if $x = \lambda$, nothing is read
  2. $v = y r$,      $\leftarrow$ means $y$ is the string popped off the stack
  3. $v' = z r$ and      $\leftarrow$ means $z$ is the string pushed onto the stack (note this corresponds to pushing one character at a time in reverse order!)
  4. $(p,x,y,q,z) \in \Delta$.      $\leftarrow$ means there is a transition from $p$ to $q$ reading $x$, popping $y$ and pushing $z$.

Of course we have our good friend $\Rightarrow_M^*$ (yields in zero or more steps) analogous to what we did for DFAs, NDFAs, and grammar derivations.

Accepting computation
Finally, of course, we need to define what it means for a machine to accept/reject a string.

Definition: Machine M = (Q,Σ,Γ,Δ,s,W) accepts string w ∈ Σ* if there exists a sequence of configurations
\[ (s,w,\lambda) \Rightarrow_M^* (q,\lambda,v) \]
where $q \in W$. If a string is not accepted, i.e. no such sequence of configurations exists, it is rejected.

Example
we looked at a nice example of a PDA last class that accepted anbn.
Now we can write down an accpeting computation of this machine as a sequence of configurations. For example given input w = aabb we have to following accepting computation:
(q0,aabb,λ) ⇒ (q1,aabb,\$) ⇒ (q1,abb,a\$) ⇒ (q1,bb,aa\$) ⇒ (q1,b,a\$) ⇒ (q1,λ,\$) ⇒ (q2,λ,λ)

Yet another Mystery Algorithm
Consider the following Mystery Algorithm:
Input: CFG G = (Σ, NT, R, S)
Output: PDA $M$ s.t. _____________________
\[ M = \left( \{q_0,q_1,q_2\},\Sigma,\Sigma \cup NT \cup \{\$\}, \Delta, q_0,\{q_2\} \right) \] where \[ \Delta = \left\{ (q_0,\lambda,\lambda,q_1,\$), (q_1,\lambda,S\$,q_2,\lambda) \right\} \cup \left\{ (q_1,\lambda,w^R,q_1,A)\ |\ (A,w) \in R \right\} \cup \left\{(q_1,x,\lambda,q_1,x) \ |\ x \in \Sigma\right\} \]

What does this algorithm output for input G = ({1,0,+},{S,B},{(S,S+B),(S,B),(B,1),(B,0)},S)?

M = ( {q0,q1,q2}, Σ, Σ ∪ NT ∪ {$}, { (q0,λ,λ,q1,\$), (q1,λ,S\$,q2,λ),
(q1,λ,B+S,q1,S), (q1,λ,B,q1,S),
(q1,λ,0,q1,B), (q1,λ,1,q1,B),
(q1,0,λ,q1,0), (q1,1,λ,q1,1),
(q1,+,λ,q1,+)
} , q0,{q2} )

Mystery Algorithm Unmasked
The Mystery Algorithm actually takes grammar G and produces a push down automaton M that accepts the language generated by G. This is a handy algorithm. For starters, it proves a nice theorem:
Theorem: If a language is generated by a CFG, it is accepted by some PDA.
Second, this means that we can specify a language with a grammar, and create an automaton to recognize strings for us. We could even imagine augmenting this machine to create a parse tree for us. However, while this machine accepts the language in theory, it's pretty useless in practice. Why? Because it is really nondeterministic. Algorithms for creating deterministic machines from input grammars is a whole big field in and of itself. This is at the heart of "parsing" for programming languages.

Ignoring the nondeterministic aspect of this mathine, though, let's see why we say that it "parses" a string. Suppose that whenever we take a transition based on the rule A ⇒ w, a transition that pops wR off the stack and replaces it with A, we annotate the new varible A with the value that it replaced. When an accepting computation completes, we'll have just popped an S off the stack that is annotated with ... the entire parse tree. The following sloppy diagram should show how that works for the simple example above and the input string 0 + 1 + 1.

Consider CFG G: \[ \begin{array}{l} S \longrightarrow S+B\ |\ B\\ B \longrightarrow 0\ |\ 1 \end{array} \]

The diagram shows the operation of the PDA $M$ produced by MysteryAlgorithm for grammar $G$, as the machine processes string $0+1+1$.

So if, given a grammar, we can make a deterministic version of the machine produced by the above Mystery Algorithm, we will be able to parse strings in the language defined by the grammar.


Christopher W Brown
Last modified: Mon Nov 2 08:38:35 EST 2009