cs302 Theory of Computation UVa Spring 2008Notes: Pushdown AutomataTuesday, 5 FebruaryUpcoming ScheduleWednesday, 6 February (9:30-10:30am): Theory Coffee Hours (Wilsdorf Coffee Shop, Imay be at one of the tables upstairs)Wednesday, 6 February (6-7pm): Problem-Solving Session (Olsson 226D)Thursday, 7 February: Problem Set 2 is due at the beginning of class.Proving Non-RegularityPumping Lemma. If A is a regular language, then there is a number p (the pumping length) wherefor any string s ∈ A and |s| ≥ p, s may be divided into three pieces, s = xyz, such that |y| > 0,|xy| ≤ p, and for any i ≥ 0, xyiz ∈ A.To use the pumping lemma to prove a language A is non-regular, assume A is regular and find acontradiction using the pumping lemma. Since the pumping lemma says that the property holdsfor any string s ∈ A, if we can find one string w ∈ A for which the property does not hold (that is,we need to show there is no way to divide w into xyz with the necessary properties) then we haveour contradiction.Example 1. Prove the language0i1j|i ≤ jis not regular.Proof by Contradiction.Assume0i1j|i ≤ jis regular and p is the pumping length for A. Then, we will identifya string that cannot be pumped.Choose w = 0p1p. w ∈ A since we can choose i = j = p.The pumping lemma says that w = xyz for some x, y, and z such that xyiz ∈ A for alli ≥ 0, and |xy| ≤ p.Since the first p symbols in w are 0s, no matter how we choose x, y, and z, we know|xy| ≤ p, so y must be withing the first p symbols of w, hence it can only contain 0s.But, since y only includes 0s, pumping y increases the number of 0s, without changingthe number of 1s. To be in the language, though, the number of 0s (i) must be ≥ thenumber of 1s (j).Thus, we have a contradiction. This proves that the language is not regular.Example 2. Prove the language {ww|w ∈ Σ∗} is not regular.Example 3. Prove the languagew|w ∈ {0, 1}∗and the number of 0s in w exceeds the number of 1sis not regular.PDA-1Pushdown AutomataA pushdown automata is a finite automaton with a stack. A stack is a data structure that can containany number of elements, but for which only the top element may be accessed. We can represent astack as a sequence of elements, [s0, s1, . . . , sn]. We use Γ (Gamma) to represent the stack alphabet.Γ is a finite set of symbols. So, a stack is represented by Γ∗.There are two operations on a stack:push: Γ∗× Γ→ Γ∗. push is defined by:push(s, ) = sfor v ∈ Γ, s = [s0, . . . , sn] , (s, v) = [v, s0, s1, . . . , sn]pop: Γ∗→ Γ∗× Γ. pop is defined by:pop([]) = ([] , )pop([s0, . . . , sn]) = (s0, [s1, . . . , sn])A deterministic pushdown automaton1(DPDA) is a 6-tuple (Q, Σ, Γ, δ, q0, F ) where Q, Σ, q0, and F aredefined as they are for a deterministic finite automaton, Γ is a finite state (the stack alphabet), andδ: Q × Σ × Γ→ Q × ΓWe can use any symbols we want in the stack alphabet, Γ. As with state labels, in designing aDPDA, it is important to give symbols names that have meaning. Typically, we use $ as a specialsymbol, often meaning the bottom of the stack.We use label arrows in a DPDA as Σ, Γ→ Γ. For a ∈ Σ, b, c ∈ Γ:• a, b → c means if the current input is a and the top-of-stack is b, follow this transition and popthe b off the stack, and push the c.• a, → c means if the current input is a, follow this transition and push c on the stack. (Itdoesn’t matter what is on the stack.)• a, b → means if the current input is a and the top-of-stack is b, follow this transition and popthe b off the stack.• a, → means if the current input is a, follow this transition (and don’t modify the stack).Here is an example DPDA - what language does it recognize?Prove that a DPDA is more powerful than a DFA.1Note that the book (Definition 2.1) defines a nondeterministic pushdown automaton, but does not define a deterministicpushdown
View Full Document
Unlocking...