Qi MiQi MiComputer Science DepartmentComputer Science DepartmentUniversity of Virginia University of Virginia 1 7-tuple: (Q, Σ, Γ, δ, q0, qaccept, qreject) Possible modifications to Turing machines?2 Consider a Turing machine with an input alphabet of {a, b, c} and another with an input alphabet of {0, 1}. Which is more powerful?| Σ | 3 Idea: Use FSM to translate the encoding between different alphabets.4. . .FSMa -> 01b -> 011c -> 0111 Encoding◦ A process of transforming information from one format into another without loss of information. Example: ◦ Binary representation of numbers Application:◦ Adding marker symbols that are not in the original alphabet when you design a TM will not change the power of TM.5 A 2-dimensional tape{L, R, U, D} Question: Is a TM with a 2-dimensional tape equivalent to one with an ordinary 1-dimensional tape?6↑↑←←XX→→↓↓The set of rational numbers:Q = { p/q | p and q are natural numbers and co-prime}The set of natural numbers:N = {1, 2, 3, 4, 5, …} True or False: |Q| > |N|?7 8Breadth-first search,instead ofdepth-first searchDovetailingDovetailing|Q| = |N| Question: Recall that adjacent cells may become non-adjacent when we map a 2-dimensional tape to a 1-dimensional tape. How do we solve the issue of mapping the head movement between adjacent cells on a 2-dimensional tape to that on a 1-dimensional tape?9 Map a 2-dimensional tape to an ordinary 1-dimensional tape. Map a k-dimensional tape to an ordinary 1-dimensional tape. Summary: ◦ Dovetailing (interleaving)◦ Mapping (1-to-1 correspondence)10 A different alphabet size Multidimensional tape Doubly-infinite tape Multiple tapes EtcTheorem: All these modifications do NOT increase the power of TM’s. –- TM robustnessQuestion: What if a combination of the above?11 Task: Design a Turing machine that can recognize {ww|w ∈ Σ*}?12 A Turing machine is deterministic if:∀ q∈Q, a∈ |δ(q,a)|≤1i.e., no multiple choices allowed Otherwise, it is non-deterministic. A non-deterministic TM (NDTM) can have several choices of which state to proceed next in a computation. Many “next-moves”:δ: Q× → 2Q× ×{L, R}13ΓΓΓ14∞15a b a a b a b a a bX X1616a b a a b a b a a bX XX Question: Is the set of languages that can be decided by NDTM’s larger than that by DTM’s?17 Simulate any non-deterministic TM N with a deterministic TM D. Three tapes: input tape, simulation tape, and address tape Have D try all possible branches of N using breadth-first search. (can’t use depth-first search here) Conclusion: NDTMs and DTMs are equivalent in power.18 An unrestricted grammar is a 4-tupleG = (V, Σ, R, S) where◦ V is a finite set of variables◦ Σ (the alphabet) is a finite set of terminal symbols◦ R is the finite set of rules. Each rule is of the formα → β, where α ∈ (V ∪ Σ)+and β ∈ (V ∪ Σ)∗◦ S ∈ V is the start symbol. V and Σ are assumed to be disjoint.19 In an unrestricted grammar (a.k.a. general grammar), the left hand side can include extra terminals and non-terminals.◦ Example: aSb → Tc Left hand side must include at least one non-terminal.20 Example: A grammar that generates {aibici| i ≥ 0}.G = (V, Σ, R, S) where V = {S, A, C}, Σ={a, b, c}R = { S → aAbc | A → aAbC | Cb → bCCc → cc }S aAbc aaAbCbc aabbCc aabbcc 21εε Question: Are unrestricted grammars as powerful as Turing machines?22 True or False: |R|>|[0, 1]| Consider a PDA having a FIFO queue instead of a stack(i.e., write-only at the top, read-only at the bottom). Does this modification change the class of languages accepted by ordinary PDA’s?
View Full Document
Unlocking...