cs302 Theory of Computation UVa Spring 2008Notes: Nondeterministic Pushdown AutomataThursday, 7 FebruaryUpcoming ScheduleNow: Problem Set 2 is due.Tuesday, 19 February: Problem Set 3 is due. PS3 will be posted before the nextclass and will cover material through the end of Chapter 2 of the textbookand Class 29 (14 February).Model of Computation for Deterministic Pushdown AutomataTo define the model of computation for a DPDA, we define the extended transition func-tion, δ∗, similarly to how we did for DFAs, except we need to model the stack.Recall that the transition function is:δ: Q × Σ × Γ→ Q × ΓWhat is the type of the extended transition function of at DPDA, δ∗:As with DFAs, we can define δ∗for all possible inputs using induction on the input string.But, we need to be careful to consider all cases for the stack transitions.δ∗(q, , s) = (q, s)For all a ∈ Σ, x ∈ Σ∗, γ ∈ Γ∗: δ∗(q, ax, γ) =1. if (qt, ) ∈ δ(q, a, ) :2. ∀hi∈ Γ, if ∧ γ = push(h, γr) :δ∗(q, ax, push(h, γr)) = (qt, push(hi, γr))3. What is missing? (left as exercise for PS3)NPDA-1Accepting State Model: A deterministic pushdown automata, A = (Q, Σ, Γ, δ, q0, F ) ac-cepts a string w ∈ Σ∗if and only if:δ∗(q0, w, []) → (qf, s) and qf∈ FWeak Empty Stack Model: A deterministic pushdown automata, A = (Q, Σ, Γ, δ, q0) (notethere is no F now) accepts a string w ∈ Σ∗if and only if:δ∗(q0,w,[])→(q,s) and s=Can all languages that can be accepted by the accepting state model be accepted by the weakempty stack model?Empty Stack Model: A deterministic pushdown automata, A = (Q, Σ, Γ, δ, q0, Z0) acceptsa string w ∈ Σ∗if and only if:δ∗(q0, w, Z0) → (q, s) and s = Challenge question: is the set of languages that can be recognized by a DPDA under theaccepting state model equivalent to the set of languages that can be recognized by a DPDAunder the empty stack model?Nondeterministic Pushdown AutomatonA nondeterministic pushdown automaton (this is what Sipser calls a pushdown automaton) isa 6-tuple (Q, Σ, Γ, δ, q0, F ) where Q, Σ, Γ, q0, F are defined as they are for DPDA and thetransition function is defined:δ : Q × Σ× Γ→Example. Define a NPDA that recognizes the language {ww|w ∈
View Full Document
Unlocking...