Slide 1Three Equivalent RepresentationsNFAs  Regular grammars Thus, the language recognized by FSA is a regular languageKleene’s TheoremSlide 5Slide 6Induction BasisInductive HypothesisInductive StepSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18In GeneralSlide 20Slide 21FoundationsAlan TuringThe Decision ProblemThe Turing MachineSlide 26Slide 27Slide 28FunctionsTuring’s TheoremFirst computers: custom computing machinesCan Machines Think?The Turing TestArtificial IntelligenceThe Church-Turning ThesisAI: The ArgumentTuring MachinesThe Language HierarchySlide 39A Turing MachineThe TapeSlide 42Slide 43Slide 44The Input StringSlide 46States & TransitionsSlide 48Slide 49Slide 50Slide 51DeterminismPartial Transition FunctionHaltingSlide 55Final StatesAcceptanceTuring Machine ExampleSlide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Infinite Loop ExampleSlide 67Slide 68Slide 69Slide 70Slide 71Another Turing Machine ExampleSlide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 87Formal Definitions for Turing MachinesSlide 89Slide 90Slide 91ConfigurationSlide 93Slide 94Slide 95Slide 96The Accepted LanguageStandard Turing MachineComputing Functions with Turing MachinesSlide 100Slide 101Slide 102Slide 103Slide 104ExampleSlide 106Slide 107Slide 108Slide 109Slide 110Slide 111Slide 112Slide 113Slide 114Slide 115Slide 116Slide 117Slide 118Slide 119Slide 120Slide 121Slide 122Slide 123Another ExampleSlide 125Slide 126Slide 127Slide 128Slide 129Slide 130Slide 131Combining Turing MachinesSlide 133Slide 1341Language Recognition (11.4)and Turing Machines (11.5)Longin Jan LateckiTemple UniversityBased on slides by Costas Busch from the coursehttp://www.cs.rpi.edu/courses/spring05/modcomp/and …2Three Equivalent RepresentationsFinite automataRegularexpressionsRegular languagesEach candescribethe othersKleene’s Theorem: For every regular expression, there is a deterministic finite-state automaton that defines the same language, and vice versa.3NFAs  Regular grammarsThus, the language recognized by FSA is a regular language Every NFA can be converted into a corresponding regular grammar and vice versa.Each symbol A of the grammar is associated with a non-terminal node of the NFA sA, in particular, start symbolS is associated with the start state sS.Every transition is associated with a grammar production: T(sA,a) = sB  A  aB.Every production B   is associated with final state sB.See Ex. 3, p. 771, and Ex. 4, p. 772.4Kleene’s TheoremLanguagesGenerated byRegular ExpressionsLanguagesRecognizedby FSA5LanguagesGenerated byRegular ExpressionsLanguagesRecognizedby FSALanguagesGenerated byRegular ExpressionsLanguagesRecognizedby FSAWe will show:6Proof - Part 1r)(rL For any regular expression the language is recognized by FSA (= is a regular language)LanguagesGenerated byRegular ExpressionsLanguagesRecognizedby FSAProof by induction on the size ofr7Induction BasisPrimitive Regular Expressions:,,NFAs)()(1 LML)(}{)(2LML )(}{)(3aLaML regularlanguagesa8Inductive HypothesisAssume for regular expressions andthat and are regular languages 1r2r)(1rL )(2rL9Inductive StepWe will prove:     112121*rLrLrrLrrLAre regular Languages10By definition of regular expressions:                  111121212121**rLrLrLrLrLrLrrLrLrLrrL11)(1rL )(2rLBy inductive hypothesis we know: and are regular languagesRegular languages are closed under:        *12121rLrLrLrLrL Union Concatenation Star We need to show:12 Therefore:               **1121212121rLrLrLrLrrLrLrLrrLAre regularlanguagesAnd trivially:))((1rLis a regular language13Proof - Part 2LanguagesGenerated byRegular ExpressionsLanguagesRecognizedby FSALrLrL )( For any regular language there is a regular expression withProof by construction of regular expression14Since is regular take the NFA that accepts it LMLML )(Single final state15From construct the equivalentGeneralized Transition Graph in which transition labels are regular expressions MExample:aba,cMaba c16Another Example:ba abb0q1q2qba,abb0q1q2qbb17Reducing the states:ba abb0q1q2qb0q2qbabb *)(* babb 18Resulting Regular Expression:0q2qbabb *)(* babb *)(**)*( bbabbabbr LMLrL  )()(19In GeneralRemoving states:iqqjqabcdeiqjqdae*bce*dce*bae*20The final transition graph:0qfq1r2r3r4r*)*(*213421rrrrrrr LMLrL  )()(The resulting regular expression:21DFA - regular languagesPush down automata - Context-freeBounded Turing M’s - Context sensitiveTuring machines - Phrase-structure Models of computing22FoundationsThe theory of computation and the practical application it made possible —the computer —was developed by an Englishman called Alan Turing.23Alan Turing1912 (23 June): Birth, Paddington, London1931-34: Undergraduate at King's College, Cambridge University1932-35: Quantum mechanics, probability, logic1936: The Turing machine, computability, universal machine1936-38: Princeton University. Ph.D. Logic, algebra, number theory 1938-39: Return to Cambridge. Introduced to German Enigma cipher machine1939-40: The Bombe, machine for Enigma decryption 1939-42: Breaking of U-boat Enigma, saving battle of the Atlantic1946: Computer and software design leading the world.1948: Manchester University1949: First serious mathematical use of a computer1950: The Turing Test for machine intelligence1952: Arrested as a homosexual, loss of security clearance1954 (7 June): Death (suicide) by cyanide poisoning, Wilmslow, Cheshire.—from Andrew Hodges http://www.turing.org.uk/turing/24The Decision ProblemIn 1928 the German mathematician, David Hilbert (1862-1943), asked whether there could be a mechanical way (i.e. by means of a fully specifiable set of instructions) of determining whether some statement in a formal system like arithmetic was provable or not.In 1936 Turing published a paper the aim of which was to show that there was no such method. “On computable numbers, with an application to the Entscheidungs problem.” Proceedings of the London Mathematical Society, 2(42):230-265).25The Turing MachineIn