Recursively Enumerable Recursive Languages

1 1 CS 301 - Lecture 23 Recursive and Recursively Enumerable Languages Fall 2008 Review Languages and Grammars Alphabets, strings, Languages Regular Languages Deterministic Finite and Nondeterministic Automata Equivalence of NFA and DFA Regular Expressions Regular Grammars Properties of Regular Languages Languages that are not regular and the pumping lemma Context Free Languages Context Free Grammars Derivations: leftmost, rightmost and derivation trees Parsing and ambiguity Simplifications and Normal Forms Nondeterministic Pushdown Automata Pushdown Automata and Context Free Grammars Deterministic Pushdown Automata Pumping Lemma for context free grammars Properties of Context Free Grammars Turing Machines Definition, Accepting Languages , and Computing Functions Combining Turing Machines and Turing s Thesis Turing Machine Variations Universal Turing Machine and Linear Bounded Automata Today: Recursive and Recursively Enumerable Languages Recursively Enumerable and Recursive Languages Definition: A language is Recursively Enumerable if some Turing machine accepts it 2 For string.

2 Let be a Recursively Enumerable language Land the Turing Machine that accepts it MLw wif then halts in a final state MLw if then halts in a non-final state Mor loops forever Definition: A language is Recursive if some Turing machine accepts it and halts on any input string In other words: A language is Recursive if there is a membership algorithm for it For string : Let be a Recursive language Land the Turing Machine that accepts it MLw wif then halts in a final state MLw if then halts in a non-final state MTuring acceptable Languages and Enumeration Procedures 3 We will prove: If a language is Recursive then there is an enumeration procedure for it A language is Recursively Enumerable if and only if there is an enumeration procedure for it (weak result) (strong result) Theorem: if a language is Recursive then there is an enumeration procedure for it LProof: MM~Enumeration Machine Accepts LEnumerates all strings of input alphabet If the alphabet is then can enumerate strings as follows: },{baM~ Enumeration procedure Repeat: M~generates a string Mwchecks if Lw YES: print to output wNO: ignore wEnd of Proof Example: M~ )(.

3 },,,{aaabbabbL=Enumeration Output : if language is Recursively Enumerable then there is an enumeration procedure for it LProof: MM~Enumeration Machine Accepts LEnumerates all strings of input alphabet 5 If the alphabet is then can enumerate strings as follows: },{baM~abaaabbabbaaaaabEnumeration procedure Repeat: M~generates a string Mwchecks if Lw YES: print to output wNO: ignore wNAIVE APPROACH Problem: If machine may loop forever Lw MM~M1wexecutes first step on BETTER APPROACH 1wM~Generates second string 2wMexecutes first step on 2wsecond step on 1wGenerates first string M~Generates third string 3wMexecutes first step on 3wsecond step on 2wthird step on 1wAnd so 6 1w2w3w4w 1 Step in string 1 1 1 2 2 2 2 3 3 3 3 If for any string machine halts in a final state then it prints on the output MiwiwEnd of Proof Theorem: If for language there is an enumeration procedure then is Recursively Enumerable LLProof: wInput Tape Enumerator for LCompare Machine that accepts L7 Turing machine that accepts LRepeat.

4 Using the enumerator, generate the next string of LFor input string w Compare generated string with wIf same, accept and exit loop End of Proof We have proven: A language is Recursively Enumerable if and only if there is an enumeration procedure for it We will prove: 1. There is a specific language which is not Recursively Enumerable (not accepted by any Turing Machine) 2. There is a specific language which is Recursively Enumerable but not Recursive Recursive Recursively Enumerable Non Recursively Enumerable 8 Some Languages Are Not Recursively Enumerable Proof Using Uncountable Sets A set is uncountable if it is not countable Definition: Theorem: Let be an infinite countable set The powerset of is uncountable S2 SSProof: Since is countable, we can write S},,,{ of S9 Elements of the powerset have the form: },{31ss},,,{ We encode each element of the power set with a binary string of 0 s and 1 s 1s2s3s4s 1000}{1sPowerset element Encoding 0110},{32ss1011},,{431sss Let s assume (for contradiction) that the powerset is countable.

5 Then: we can enumerate the elements of the powerset 10000110001101011001 Powerset element Encoding 1t2t3t4t 10 Take the powerset element whose bits are the complements in the diagonal 100001100011010110011t2t3t4t New element: ..0011(birary complement of diagonal) The new element must be some of the powerset itHowever, that s impossible: the i-th bit of must be the complement of itself from definition of ititContradiction!!! Since we have a contradiction: The powerset of is uncountable S2S11 An Application: Languages Example Alphabet : },{baThe set of all Strings: },,,,,,,,,{},{*..aabaaabbbaabaababaS ==infinite and countable Example Alphabet : },{baThe set of all Strings: },,,,,,,,,{},{*..aabaaabbbaabaababaS ==infinite and countable A language is a subset of : },,{aababaaL=SExample Alphabet : },{baThe set of all Strings: },,,,,,,,,{},{*.

6 AabaaabbbaabaababaS ==infinite and countable The powerset of contains all Languages : }},,,}{,{},{},{{ =1L2L3L4 Luncountable SLanguages: uncountable Turing machines: countable 1L2L3 LkL1M2M3M ?There are more Languages than Turing Machines 12 There are some Languages not accepted by Turing Machines (These Languages cannot be described by algorithms) Conclusion: Languages Accepted by Turing Machines Languages not accepted by Turing Machines kLA Language which is not Recursively Enumerable We want to find a language that is not Recursively Enumerable This language is not accepted by any Turing Machine 13 Consider alphabet }{aStrings: ..,,,,aaaaaaaaaa1a2a3a4a Consider Turing Machines that accept Languages over alphabet }{aThey are countable: ..,,,,4321 MMMME xample language accepted by },,{)(aaaaaaaaaaaaMLi=},,{)(642aaaMLi=iM Alternative representation 1a2a3a4a5a6a7a)(iML 0111000 1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 014 Consider the language )}(:{iiiMLaaL =Lconsists from the 1 s in the diagonal 1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0},,{ the language )}(:{iiiMLaaL =Lconsists of the 0 s in the diagonal )}(:{iiiMLaaL =L1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0},,{ Theorem: Language is not Recursively Enumerable LProof: is Recursively Enumerable LAssume for contradiction that There must exist some machine that accepts kMLLMLk=)(1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0 Question: ?

7 1 MMk=1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0 Answer: 1 MMk )()(111 MLaMLak 16 1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0 Question: ?2 MMk=1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0 Answer: 2 MMk )()(222 MLaMLak 1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0 Question: ?3 MMk=1a2a3a4a)(1ML 0110 )(2ML)(3ML0101 0111 )(4ML010 0 Answer: 3 MMk )()(333 MLaMLak 17 Similarly: ikMM )()(iikiMLaMLa )()(iikiMLaMLa for any iBecause either: or Therefore, the machine cannot exist kMTherefore, the language is not Recursively Enumerable LEnd of Proof Observation: There is no algorithm that describes L(otherwise would be accepted by some Turing Machine) LRecursive Recursively Enumerable Non Recursively Enumerable L18 What s Next Read Linz Chapter 1, , , , (skip ), 3, 4, 5, , , (skip ), , , , (skip ), 8, 9, 10, 11 JFLAP Chapter 1, , (skip ), 3, 4, 5, 6, 7, (skip 8), 9, (skip 10), 11 Next Lecture Topics From , , , and More Recursive Languages , Unrestricted Grammars, Context Sensitive Grammars, and the Chomsky Hierarchy Quiz 3 in Recitation on Wednesday 11/12 Covers Linz , , , (skip ), 8, and JFLAP 5,6,7 Closed book, but you may bring one sheet of x 11 inch paper with any notes you like.

8 Quiz will take the full hour Homework Homework Due Thursday