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.
- $u = xu'$, $\leftarrow$ means $x$ is the character read or, if $x = \lambda$, nothing is read
- $v = y r$, $\leftarrow$ means $y$ is the string popped off the stack
- $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!)
- $(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.
\[ (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.
Now we can write down an accepting 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,λ,λ)
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}
)
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 machine,
though, let's see why we say that it "parses" a string.
Suppose that whenever we take a transition
based on the rule $A\rightarrow w$, a transition
that pops $w^R$
off the stack and replaces it with A, we
annotate the new variable 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.
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.