# Class 27: Converting Grammars to PDAs

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

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.

For machine 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.

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
A machine is allowed to go from one configuration to another provided there is a transition that allows it. We mnake that idea formal with the following:

For machine M = (Q,Σ,Γ,Δ,s,W), configuration (p,u,v) yields (q,u',v') in 1 step (which we write as (p,u,v) ⇒ (q,u',v')) provided that (p,x,y,q,z) ∈ Δ, where u = xu' and x ∈ Σ ∪ {λ}, v = y r and v' = z r, where r,y,z ∈ Γ *.

Accepting computation
Machine M = (Q,Σ,Γ,Δ,s,W) accepts string w ∈ Σ* if there exists a sequence of configurations
(s,w,λ) ⇒ (p1,u1,v1) ⇒ ... ⇒ (pn,un,vn)
where pn ∈ W and un = λ. 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: G = (Σ, NT, R, S)
Output: M = ({q0,q1,q2}, Σ,Σ ∪ NT ∪ {\$}, q0, {(q0,λ,λ,q1,\$), (q1,λ,S\$,q2,λ} ∪ {(q1,λ,wR,q1,A) | (A,w) ∈ R} ∪ {(q1,x,λ,q1,x) | x ∈ Σ}, {q2})
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} )