Report

Turing machines Sipser 2.3 and 3.1 (pages 123-144) A Context-free Grammar for {anbncn| n ≥ 0}? • Theorem 2.34 (Pumping lemma for CFLs): If A is a CFL, then there is a number p where, if s is any string in A of length ≥ p, then s = uvxyz such that: 1. For each i ≥ 0, uvixyiz ∈ A, 2. |vy| > 0, and 3. |vxy| ≤ p CS 311 Mount Holyoke College 2 Proof idea • Surgery on parse trees CS 311 Mount Holyoke College 3 So… • Is {anbncn| n ≥ 0} a CFL? CS 311 Mount Holyoke College 4 Chomsky hierarchy anbncn Context-free languages Regular languages CS 311 Mount Holyoke College 0n1n 5 Introducing… Turing machines Infinite tape a b a b ⨆ ⨆ ⨆ Bi-directional read/write head Finite control CS 311 Mount Holyoke College 6 Formally… • A Turing machine is a 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject), where – Q is a finite set called the states – Σ is a finite set not containing the blank symbol ⨆ called the input alphabet – Γ is a finite set called the tape alphabet with ⨆∈Γ and Σ⊆Γ – δ:Q ×Γ → Q ×Γ ×{L,R} – q0∈Q is the start state – qaccept∈Q is the accept state – qaccept∈Q is the reject state CS 311 Mount Holyoke College 7 Recognizing {anbncn| n ≥ 0} Infinite tape a a b b c c ⨆ ⨆ ⨆ Finite control CS 311 Mount Holyoke College 8 Configurations • A configuration is – Current state – Current tape contents – Current head location • u q v means – Current state is q – Current tape contents is uv – Current head points at first symbol of v • Example – – – – âaq1bbcc In state q1 Tape contents are âabbcc Tape head is on first b CS 311 Mount Holyoke College 9 Yields • A configuration C1 yields configuration C2 if the Turing machine can legally go from C1 to C2 in a single step • • Written yields ⊢ CS 311 Mount Holyoke College 10 Turing-recognizable languages • A Turing machine accepts input w if a sequence of configurations C1,C2,...,Ck exists where 1. C1 is the start configuration of M on input w 2. Each Ci yields Ci+1 3. Ck is an accepting configuration • Defn 3.5: A language is Turing-recognizable if it is accepted by some Turing machine. CS 311 Mount Holyoke College 11 Recognizing CS 311 Mount Holyoke College . 12