Lecture Notes 25 Grammars and Turing Machines 1 Grammars and Turing Machines Do Homework 20. Grammars, Recursively Enumerable Languages, and Turing Machines L Unrestricted Grammar Accepts Unrestricted Grammars An unrestricted, or Type 0, or phrase structure grammar G is a quadruple (V, Σ, R, S), where • V is an alphabet, • Σ (the set of terminals) is a subset of V, • R (the set of rules) is a finite subset of • (V* (V-Σ) V*) × V*, context N context → result • S (the start symbol) is an element of V - Σ. We define derivations just as we did for context-free grammars. The language generated by G is {w ∈ Σ* : S ÞG* w} There is no notion of a derivation tree or rightmost/leftmost derivation for unrestricted grammars. Unrestricted Grammars Example: L = anbncn, n > 0 S → aBSc S → aBc Ba → aB Bc → bc Bb → bb Another Example L = {w ∈ {a, b, c}+ : number of a's, b's and c's is the same} S → ABCS S → ABC AB → BA BC → CB AC → CA BA → AB CA → AC CB → BC A → a B → b C → cRecursively Enumerable Language Turing MachineLecture Notes 25 Grammars and Turing Machines 2 A Strong Procedural Feel Unrestricted grammars have a procedural feel that is absent from restricted grammars. Derivations often proceed in phases. We make sure that the phases work properly by using nonterminals as flags that we're in a particular phase. It's very common to have two main phases: • Generate the right number of the various symbols. • Move them around to get them in the right order. No surprise: unrestricted grammars are general computing devices. Equivalence of Unrestricted Grammars and Turing Machines Theorem: A language is generated by an unrestricted grammar if and only if it is recursively enumerable (i.e., it is semidecided by some Turing machine M). Proof: Only if (grammar → TM): by construction of a nondeterministic Turing machine. If (TM → grammar): by construction of a grammar that mimics backward computations of M. Proof that Grammar →→→→ Turing Machine Given a grammar G, produce a Turing machine M that semidecides L(G). M will be nondeterministic and will use two tapes: à ❑ a b a ❑ ❑ à 0 1 0 0 0 0 0 ❑ ❑ à a S T a b ❑ 0 1 0 0 0 0 0 For each nondeterministic "incarnation": • Tape 1 holds the input. • Tape 2 holds the current state of a proposed derivation. At each step, M nondeterministically chooses a rule to try to apply and a position on tape 2 to start looking for the left hand side of the rule. Or it chooses to check whether tape 2 equals tape 1. If any such machine succeeds, we accept. Otherwise, we keep looking.Lecture Notes 25 Grammars and Turing Machines 3 Proof that Turing Machine →→→→ Grammar Suppose that M semidecides a language L (it halts when fed strings in L and loops otherwise). Then we can build M' that halts in the configuration (h, à❑). We will define G so that it simulates M' backwards. We will represent the configuration (q, àuaw) as >uaqw< M' goes from à ❑ a b b a ❑ ❑ ❑ à ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ Then, if w ∈ L, we require that our grammar produce a derivation of the form S ÞG >❑h< (produces final state of M') ÞG* >❑abq< (some intermediate state of M') ÞG* >❑sw< (the initial state of M') ÞG w< (via a special rule to clean up >❑s) ÞG w (via a special rule to clean up <) The Rules of G S → >❑h< (the halting configuration) >❑s → ε (clean-up rules to be applied at the end) < → ε Rules that correspond to δ: If δ(q, a) = (p, b) : bp → aq If δ(q, a) = (p, →) : abp → aqb ∀b ∈ Σ a❑p< → aq< If δ(q, a) = (p, ←), a ≠ ❑ pa → aq If δ(q, ❑) = (p, ←) p❑b → ❑qb ∀b ∈ Σ p< → ❑q<Lecture Notes 25 Grammars and Turing Machines 4 A REALLY Simple Example M' = (K, {a}, δ, s, {h}), where δ ={ ((s, ❑), (q, →)), 1 ((q, a), (q, →)), 2 ((q, ❑), (t, ←)), 3 ((t, a), (p, ❑)), 4 ((t, ❑), (h, ❑)), 5 ((p, ❑), (t, ←)) 6 L = a* S →>❑h< >❑s → ε < → ε (1) ❑❑q→ ❑s❑ ❑aq → ❑sa ❑❑q< → ❑s< (2) a❑q → aq❑ aaq → aqa a❑q< → aq< (3) t❑❑ → ❑q❑ t❑a → ❑qa t< → ❑q< (4) ❑p → at (5) ❑h → ❑t (6) t❑❑ → ❑p❑ t❑a → ❑pa t< → ❑p< Working It Out S →>❑h< 1 >❑s → ε 2 < → ε 3 (1) ❑❑q→ ❑s❑ 4 ❑aq → ❑sa 5 ❑❑q< → ❑s< 6 (2) a❑q → aq❑ 7 aaq → aqa 8 a❑q< → aq< 9 (3) t❑❑ → ❑q❑ 10 t❑a → ❑qa 11 t< → ❑q< 12 (4) ❑p → at 13 (5) ❑h → ❑t 14 (6) t❑❑ → ❑p❑ 15 t❑a → ❑pa 16 t< → ❑p< 17 >❑saa< 1 >❑aqa< 2 >❑aaq< 2 >❑aa❑q< 3 >❑aat< 4 >❑a❑p< 6 >❑at< 4 >❑❑p< 6 >❑t< 5 >❑h< S Þ >❑h< 1 Þ >❑t< 14 Þ >❑❑p< 17 Þ >❑at< 13 Þ >❑a❑p< 17 Þ >❑aat< 13 Þ >❑aa❑q< 12 Þ >❑aaq< 9 Þ >❑aqa< 8 Þ >❑saa< 5 Þ aa< 2 Þ aa 3Lecture Notes 25 Grammars and Turing Machines 5 An Alternative Proof An alternative is to build a grammar G that simulates the forward operation of a Turing machine M. It uses alternating symbols to represent two interleaved tapes. One tape remembers the starting string, the other “working” tape simulates the run of the machine. The first (generate) part of G: Creates all strings over Σ* of the form w = à à ❑ ❑ Qs a1 a1 a2 a2 a3 a3 ❑ ❑ … The second (test) part of G simulates the execution of M on a particular string w. An example of a partially derived string: à à ❑ ❑ a 1 b 2 c c b 4 Q3 a 3 Examples of rules: b b Q 4 → b 4 Q 4 (rewrite b as 4) b 4 Q 3 → Q 3 b 4 (move left) The third (cleanup) part of G erases the junk if M ever reaches h. Example rule: # h a 1 → a # h (sweep # h to the right erasing the working “tape”) Computing with Grammars We say that G computes f if, for all w, v ∈Σ*, SwS
View Full Document
Unlocking...