07-Lecture PDF - Context-Sensitive Grammars

Administrivia Results from first midterm Feedback: please fill out today Second midterm exam date: vote today Reading: Chapter 4 Last time: TMs, Decidable problems Today: Context-Sensitive Grammars, LBAs, decidable, recognizable, undecidable language...

Administrivia Results from first midterm Feedback: please fill out today Second midterm exam date: vote today Reading: Chapter 4 Last time: TMs, Decidable problems Today: Context-Sensitive Grammars, LBAs, decidable, recognizable, undecidable languages Context-sensitive grammars Recall a context-free grammar’s rules are of the form α → β, where α is a single variable and β is a string of variables and terminals. Ex: S →E |F E → 0E 0 | 1E 1 |  F → 0F 0 | 1F 1 | 0 | 1 A context-sensitive grammar (CSG) requires that substitutions of variables are surrounded by some “context” on either or both sides Context-sensitive grammars (Type 1 grammars) Definition A context-sensitive grammar is a 4-tuple (V , Σ, R, S), where: 1 V is a finite set of variables, 2 Σ is a finite set of terminals, Σ ∩ V = ∅ 3 R is a finite set of rules of the form αAβ → αγβ where A ∈ V , α, β ∈ (V ∪ Σ)∗ , and γ ∈ (V ∪ Σ)+ 4 S ∈ V is the start variable 5 S →  is permitted A context-sensitive language is a language which is generated by a CSG. Theorem All context-free languages are context-sensitive. CSG example Consider the following language: L = {ai b j c k | 1 ≤ i ≤ j ≤ k}. We will construct a CSG for it. Main idea: Start by constructing a CFG for the language {ai (bc)j c k−j | 1 ≤ i ≤ j ≤ k}, then swap b’s and c’s using CSG rules CSG example CFG for {ai (bc)j c k−j | 1 ≤ i ≤ j ≤ k}: S → TXC T → aTbc | abc X → bcX |  C → cC |  How do we swap b’s and c’s? We could add cb → bc but this is not in the form of a CSG. CSG example Solution: use variables B and C instead of terminals b and c, then use CSG rules to simulate a swap: S → TXC T → aT BC | aBC X → BC X |  C → CC |  This generates strings such as aBC , aaBCBCBCC , etc. CSG example We want to simulate a swap CB → BC. Add the rules: CB → CD CD → ED ED → EC EC → BC CSG example We want to simulate a swap CB → BC. Add the rules: CB → CD CD → ED ED → EC EC → BC Lastly we need to convert B’s to b’s and C ’s to c’s. CSG example We want to simulate a swap CB → BC. Add the rules: CB → CD CD → ED ED → EC EC → BC Lastly we need to convert B’s to b’s and C ’s to c’s. CSG example We only want to do this conversion when we have a string of the form ai B j C k where 1 ≤ i ≤ j ≤ k. Add the rules: aB → ab bB → bb bC → bc cC → cc CSG example Our grammar looks like: CB → CD CD → ED ED → EC S → TXC EC → BC T → aTBC | aBC aB → ab X → BCX |  bB → bb C → CC |  bC → bc cC → cc Lastly we remove the -transitions X →  and C → : CSG example CSG for {ai b j c k | 1 ≤ a ≤ b ≤ c}: CB → CD CD → ED ED → EC S → TXC | TC | TX | T EC → BC T → aTBC | aBC | aTB | aB aB → ab X → BCX | BC | BX | B bB → bb C → CC bC → bc cC → cc Linearly Bounded Automata Definition A linear bounded automaton is a type of a TM where the tape head is restricted only to the input. If the machine tries to move its head off either end of the input, the head stays where it is. Schematic Finite Automaton Schematic Pushdown Automaton Schematic Turing Machine Linearly Bounded Automaton LBA’s Can we construct an LBA which decides L = {ai b j c k | 1 ≤ a ≤ b ≤ c}? Theorem A language L is context-sensitive iff there exists an LBA M such that L(M) = L. Theorem All context-free languages are context-sensitive. Theorem All context-sensitive languages are decidable languages. Recall the Notion of Decidability From last lecture: Theorem ADFA = {< B, w > |B is a DFA that accepts input string w } is decidable. Theorem ANFA = {< B, w > |B is a NFA that accepts input string w } is decidable. Theorem EDFA = {< A > |A is a DFA and L(A) = ∅} is decidable. Theorem EQDFA = {< A, B > |A and B are DFAs and L(A) = L(B)} is decidable. Some Decidable Grammar Problems Theorem ACFG = {< G , w > |G is a CFG that generates string w } is decidable. Proof. Convert G into CNF. Then check all derivations with exactly 2n − 1 steps, where |w | = n. S =“On input < G , w >, where G is a CFG and w is a string: 1 Convert G to an equivalent grammar in CNF. 2 List all derivations with 2n − 1 steps, where |w | = n. 3 If any of these derivations generate w , accept; otherwise, reject.” Note: this is relevant when compiling programs. CFLs ⊂ Decidable Languages Theorem Every context-free language is decidable. Proof. let A be a CFL convert the PDA for A into a TM (simulating a stack with the TM’s more versatile tape is easy) he PDA for A may be nondeterministic, but we can convert it into a nondeterministic TM and we know that any NTM can be converted into an equivalent DTM CFLs ⊂ Decidable Languages Theorem Every context-free language is decidable. Proof. let A be a CFL convert the PDA for A into a TM (simulating a stack with the TM’s more versatile tape is easy) he PDA for A may be nondeterministic, but we can convert it into a nondeterministic TM and we know that any NTM can be converted into an equivalent DTM This approach is flawed! some branches of the PDA’s computation may go on forever, reading and writing the stack without ever halting the simulating TM then would also have some non-halting branches in its computation, and so the TM would not be a decider CFLs ⊂ Decidable Languages Theorem Every context-free language is decidable. Proof. We’ve already done it! Let L be a CFL and G a CFG for it. There is a simple TM that decides L: MG = “On input w : 1 Run TM S on input < G , w >. 2 If this machine accepts, accept; if it rejects, reject.” Recall that TM S decides ACFG = {< G , w > |G is a CFG that generates string w } is decidable. Language Hierarchy Not all Decidable Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) = L(G2 )} is undecidable. Why can’t we use the symmetric difference, as we did for regular languages? Not all Decidable Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) = L(G2 )} is undecidable. Why can’t we use the symmetric difference, as we did for regular languages? The symmetric difference approach for regular languages (EDFA ) relied on several closure properties. Are CFLs closed under union? Not all Decidable Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) = L(G2 )} is undecidable. Why can’t we use the symmetric difference, as we did for regular languages? The symmetric difference approach for regular languages (EDFA ) relied on several closure properties. Are CFLs closed under union? Are CFLs closed under intersection? Not all Decidable Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) = L(G2 )} is undecidable. Why can’t we use the symmetric difference, as we did for regular languages? The symmetric difference approach for regular languages (EDFA ) relied on several closure properties. Are CFLs closed under union? Are CFLs closed under intersection? Consider: L1 = {am b n c m |m ≥ n ≥ 0} and L2 = {am b n c m |n ≥ m ≥ 0} and L3 = L1 ∩ L2 Not all Decidable Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) = L(G2 )} is undecidable. Why can’t we use the symmetric difference, as we did for regular languages? The symmetric difference approach for regular languages (EDFA ) relied on several closure properties. Are CFLs closed under union? Are CFLs closed under intersection? Consider: L1 = {am b n c m |m ≥ n ≥ 0} and L2 = {am b n c m |n ≥ m ≥ 0} and L3 = L1 ∩ L2 Are CFLs closed under complementation? But this is not a proof that EQCFG is undecidble... Not all Recognizable Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) = L(G2 )} is not T-recognizable. Theorem EQCFG = {< G1 , G2 > |G1 , G2 are CFGs and L(G1 ) 6= L(G2 )} is T-recognizable. Proof. Convert both into CNF. Generate all strings over Σ in lexicographical order. If the two grammars ever disagree, accept; otherwise, reject” EQCFG is an example of co-Turing-recognizable language. Not all Decidable Theorem ADFA = {< B, w > |B is a DFA that accepts input string w } is decidable. Theorem APDA = {< B, w > |B is a PDA that accepts input string w } is decidable. Theorem ATM = {< B, w > |B is a TM that accepts input string w } is undecidable. The Universal TM Theorem ATM = {< M, w > |M is a TM that accepts input string w } is recognizable. Proof. U = “On input < M, w >, where M is a TM and w is a string: 1 Simulate M on input w. 2 If M ever enters its accept state, accept; if M ever enters its reject state, reject.” Why is this not a decider? This is the famous “universal machine;” it played an important role in the development of stored-program computers and is the inspiration for the “von Neumann computer architecture”. ATM simulates any other TM M from M’s description. Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” What does D do when it’s given < D > as input? D(< D >) accepts if D doesn’t accept < D > and rejects if D accepts < D >. No matter what D does, it is forced to do the opposite, which is a contradiction. A Useful Property Theorem A language is decidable if and only it is Turing-recognizable and co-Turing-recognizable. Proof. ⇒) Let L be decidable and M the decider for it. Then M is a recognizer for L and by swapping the accept and reject states in M to obtain M 0 we now have a recognizer for L. ⇐ ) Let L be a recognizable language with M1 as its recognizer. Let L be recognizable with M2 as its recognizer. Then we can build a decider M for L by simulating M1 and M2 in parallel, one step at a time: M = “On input w : 1 Run M1 and M2 in parallel 2 If M1 accepts, accept; if M2 accepts, reject.” A Language that is not T-recognizable Theorem ATM is not T-recognizable Proof. Suppose ATM is T-recognizable and M1 is its recognizer. We have shown that ATM is in fact T-recognizable and let M2 be its recognizer. Then by running M1 and M2 in parallel, we can decide ATM , which is a contradiction. A Language that is not T-recognizable Theorem ATM is not T-recognizable Proof. Suppose ATM is T-recognizable and M1 is its recognizer. We have shown that ATM is in fact T-recognizable and let M2 be its recognizer. Then by running M1 and M2 in parallel, we can decide ATM , which is a contradiction. Wait, what did we just do here? Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof Sketch. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof Sketch. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof Sketch. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” What does D do when it’s given < D > as input? Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof Sketch. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” What does D do when it’s given < D > as input? D(< D >) accepts if D doesn’t accept < D > and rejects if D accepts < D >. Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof Sketch. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” What does D do when it’s given < D > as input? D(< D >) accepts if D doesn’t accept < D > and rejects if D accepts < D >. No matter what D does, it is forced to do the opposite, which is a contradiction. Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof Sketch. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” What does D do when it’s given < D > as input? D(< D >) accepts if D doesn’t accept < D > and rejects if D accepts < D >. No matter what D does, it is forced to do the opposite, which is a contradiction.No such H exists! Paradox [The Barber Paradox] Consider a small village where the barber has a sign in his shop: “I shave all those, and those only, who do not shave themselves.” Paradox [The Barber Paradox] Consider a small village where the barber has a sign in his shop: “I shave all those, and those only, who do not shave themselves.” The question is, does the barber shave himself? Paradox [The Barber Paradox] Consider a small village where the barber has a sign in his shop: “I shave all those, and those only, who do not shave themselves.” The question is, does the barber shave himself? The barber cannot shave himself as he only shaves those who do not shave themselves. Thus, if he shaves himself he cannot be the barber who shaves those who do not shave themselves. Conversely, if the barber does not shave himself, then he fits into the group of people who would be shaved by the barber, and thus, as the barber, he must shave himself. Paradox [The Barber Paradox] Consider a small village where the barber has a sign in his shop: “I shave all those, and those only, who do not shave themselves.” The question is, does the barber shave himself? The barber cannot shave himself as he only shaves those who do not shave themselves. Thus, if he shaves himself he cannot be the barber who shaves those who do not shave themselves. Conversely, if the barber does not shave himself, then he fits into the group of people who would be shaved by the barber, and thus, as the barber, he must shave himself. What’s the way out of this paradox? Paradox [The Barber Paradox] Consider a small village where the barber has a sign in his shop: “I shave all those, and those only, who do not shave themselves.” The question is, does the barber shave himself? The barber cannot shave himself as he only shaves those who do not shave themselves. Thus, if he shaves himself he cannot be the barber who shaves those who do not shave themselves. Conversely, if the barber does not shave himself, then he fits into the group of people who would be shaved by the barber, and thus, as the barber, he must shave himself. What’s the way out of this paradox? No such barber can exist! Russell’s Paradox [Russell’s Paradox] Consider the set of all sets that are not members of themselves. x = {a : a is not in a} Russell’s Paradox [Russell’s Paradox] Consider the set of all sets that are not members of themselves. x = {a : a is not in a} Is the set of sets that are not members of themselves a member of this set? That is, is x ∈ x? Long and interesting history Dates back to the 1800s Leads to inconsistency in set theory Russell on Russell’s Paradox I was led to this contradiction by considering Cantor’s proof that there is no greatest cardinal number. I thought, in my innocence, that the number of all the things there are in the world must be the greatest possible number, and I applied his proof to this number to see what would happen. This process led me to the consideration of a very peculiar class. Thinking along the lines which had hitherto seemed adequate, it seemed to me that a class sometimes is, and sometimes is not, a member of itself. The class of teaspoons, for example, is not another teaspoon, but the class of things that are not teaspoons, is one of the things that are not teaspoons. There seemed to be instances that are not negative: for example, the class of all classes is a class. The application of Cantor’s argument led me to consider the classes that are not members of themselves; and these, it seemed, must form a class. I asked myself whether this class is a member of itself or not. If it is a member of itself, it must possess the defining property of the class, which is to be not a member of itself. If it is not a member of itself, it must not possess the defining property of the class, and therefore must be a member of itself. Thus each alternative leads to its opposite and there is a contradiction. Russell on Russell’s Paradox At first I thought there must be some trivial error in my reasoning. I inspected each step under logical microscope, but I could not discover anything wrong. I wrote to Frege about it, who replied that arithmetic was tottering and that he saw that his Law V was false. Frege was so disturbed by this contradiction that he gave up the attempt to deduce arithmetic from logic, to which, until then, his life had been mainly devoted. Like the Pythagoreans when confronted with incommensurables1 he took refuge in geometry and apparently considered that his life’s work up to that moment had been misguided. Bertrand Russell, “My Philosophical development”, Chapter VII Principia Mathematica: Philosophical Aspects. New York: Simon and Schuster, 1959. 1 Pythagoreans believed that all numbers can be expressed as ratios√ of integers, aka, rationals. The discovery of irrational numbers such as 2, π, e shows this is not true. Comparing Infinities Definition The size of a finite set (its cardinality) is simply the number of elements in it. Comparing Infinities Definition The size of a finite set (its cardinality) is simply the number of elements in it. E.g., {1, 3, 5, 7} has size 4 and {a, b, c} has size 3. Comparing Infinities Definition The size of a finite set (its cardinality) is simply the number of elements in it. E.g., {1, 3, 5, 7} has size 4 and {a, b, c} has size 3. Definition A function f : A → B, where A and B are sets, is 1-to-1 if it never maps two different elements to the same place. i.e., if f (a) 6= f (b) whenever a 6= b. The function f is onto if it hits every element of B, i.e., if for every b ∈ B there is an a ∈ A such that f (a) = b. Then sets A and B are the same size if there is a one-to-one, onto function f : A → B. A function that is both one-to-one and onto is called a correspondence. Comparing Infinities Definition The size of a finite set (its cardinality) is simply the number of elements in it. E.g., {1, 3, 5, 7} has size 4 and {a, b, c} has size 3. Definition A function f : A → B, where A and B are sets, is 1-to-1 if it never maps two different elements to the same place. i.e., if f (a) 6= f (b) whenever a 6= b. The function f is onto if it hits every element of B, i.e., if for every b ∈ B there is an a ∈ A such that f (a) = b. Then sets A and B are the same size if there is a one-to-one, onto function f : A → B. A function that is both one-to-one and onto is called a correspondence. Note 1-to-1 is also called injective, onto is also called surjective and correspondence is also called bijection. Counting Infinities Claim The size of the set of odd natural numbers equals the size of the set of all natural numbers. Counting Infinities Claim The size of the set of odd natural numbers equals the size of the set of all natural numbers. Proof. Let N = {1, 2, 3... } and O = {1, 3, 5,... }. All we need to do is find a bijection f : N → O. Counting Infinities Claim The size of the set of odd natural numbers equals the size of the set of all natural numbers. Proof. Let N = {1, 2, 3... } and O = {1, 3, 5,... }. All we need to do is find a bijection f : N → O. f (n) = 2n − 1 Counting Infinities Claim The size of the set of odd natural numbers equals the size of the set of all natural numbers. Proof. Let N = {1, 2, 3... } and O = {1, 3, 5,... }. All we need to do is find a bijection f : N → O. f (n) = 2n − 1 Definition A set is countable if it is either finite or the same size as N. Claim The set ALUE = {42, 84, 126,... } is countable. Counting Infinities Claim The size of the set of odd natural numbers equals the size of the set of all natural numbers. Proof. Let N = {1, 2, 3... } and O = {1, 3, 5,... }. All we need to do is find a bijection f : N → O. f (n) = 2n − 1 Definition A set is countable if it is either finite or the same size as N. Claim The set ALUE = {42, 84, 126,... } is countable. Proof. f (n) = 42n Counting Infinities Claim the set of positive rational numbers Q = { m n |m, n ∈ N} is countable. Proof. Uncountable Infinities Claim The set of real numbers R is uncountable Proof. Suppose R is countable and f : N → R is a bijection. Then consider the pairs (N, R) in that correspondence and construct a special “diagonal” real number d (0 < d < 1) as follows: n f (n) 1 1.41421... 2 42.00000... 3 3.14159... 4 2.71828... 5 6.62607......... d = 0.51238... and d is never paired with a natural number (by construction). Proving ATM is Undecidable Theorem ATM = {< M, w > |M is a TM that accepts input w } is undecidable. Proof. Suppose ATM is decidable and let H be its decider. Then H(< M, w >) = accept if M accepts w and H(< M, w >) = reject, if M does not accept w. Construct TM D that uses H as a subroutine. D = “On input < M >, where M is a TM: 1 Run H on input < M, < M >>. 2 Output the opposite of what H outputs, i.e., if H accepts, reject; and if H rejects, accept.” What does D do when it’s given < D > as input? D(< D >) accepts if D doesn’t accept < D > and rejects if D accepts < D >. No matter what D does, it is forced to do the opposite, which is a contradiction. Proving ATM is Undecidable: More Details ( accept if M accepts w H(< M, w >) = reject if M rejects w ( accept if M doesn’t accept < M > D(< M >) = reject if M accepts < M > ( accept if D doesn’t accept < D > D(< D >) = reject if D accepts < D > Proving ATM is Undecidable: More Details < M1 > < M2 > < M3 > < M4 >... M1 accept accept... M2 accept accept... M3 accept accept......... < M1 > < M2 > < M3 > < M4 >... M1 accept reject reject accept... M2 accept reject accept reject... M3 reject accept reject accept......... < M1 > < M2 > < M3 >...... M1 accept reject reject... accept... M2 accept reject accept... reject... M3 reject accept reject... accept......... D reject accept accept... ???......... A Useful Property Theorem A language is decidable if and only it is Turing-recognizable and co-Turing-recognizable. Proof. ⇒) Let L be decidable and M the decider for it. Them M is a recognizer for L and by swapping the accept and reject states in M to obtain M 0 we now have a recognizer for L. ⇐ ) Let L be a recognizable language with M1 as its recognizer. Let L be recognizable with M2 as its recognizer. Then we can build a decider M for L by simulating M1 and M2 in parallel, one step at a time: M = “On input w : 1 Run M1 and M2 in parallel 2 If M1 accepts, accept; if M2 accepts, reject.” A Language that is not T-recognizable Theorem ATM is not T-recognizable Proof. Suppose ATM is T-recognizable and M1 is its recognizer. We have shown that ATM is in fact T-recognizable and let M2 be its recognizer. Then by running M1 and M2 in parallel, we can decide ATM , which is a contradiction. The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. Use the bijection to construct one sequence that differs from every sequence on the right hand side (by flipping the i-th bit in the i-th sequence). The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. Use the bijection to construct one sequence that differs from every sequence on the right hand side (by flipping the i-th bit in the i-th sequence). (2) We show that any language has a unique characteristic sequence, which is an infinite binary string. The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. Use the bijection to construct one sequence that differs from every sequence on the right hand side (by flipping the i-th bit in the i-th sequence). (2) We show that any language has a unique characteristic sequence, which is an infinite binary string. Σ∗ = { , 0, 1, 00, 01, 10, 11, 000, 001,... } O= { 1, 01, 11, 001,... } XO = 0 0 1 0 1 0 1 0 1... The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. Use the bijection to construct one sequence that differs from every sequence on the right hand side (by flipping the i-th bit in the i-th sequence). (2) We show that any language has a unique characteristic sequence, which is an infinite binary string. Σ∗ = { , 0, 1, 00, 01, 10, 11, 000, 001,... } O= { 1, 01, 11, 001,... } XO = 0 0 1 0 1 0 1 0 1... The set of all languages has the same size as B, The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. Use the bijection to construct one sequence that differs from every sequence on the right hand side (by flipping the i-th bit in the i-th sequence). (2) We show that any language has a unique characteristic sequence, which is an infinite binary string. Σ∗ = { , 0, 1, 00, 01, 10, 11, 000, 001,... } O= { 1, 01, 11, 001,... } XO = 0 0 1 0 1 0 1 0 1... The set of all languages has the same size as B, which is uncountable, The Set of All Languages is Uncountable Theorem The set of all languages is uncountable. Proof. (1) We can show that the set of all infinite binary sequences B is uncountable, using the same idea as before. Suppose it is countable: we have a bijection with N. Use the bijection to construct one sequence that differs from every sequence on the right hand side (by flipping the i-th bit in the i-th sequence). (2) We show that any language has a unique characteristic sequence, which is an infinite binary string. Σ∗ = { , 0, 1, 00, 01, 10, 11, 000, 001,... } O= { 1, 01, 11, 001,... } XO = 0 0 1 0 1 0 1 0 1... The set of all languages has the same size as B, which is uncountable, so it is also uncountable. TMs and Problems Theorem The set of all Turing Machines is countable. TMs and Problems Theorem The set of all Turing Machines is countable. Theorem The set of all languages is uncountable. TMs and Problems Theorem The set of all Turing Machines is countable. Theorem The set of all languages is uncountable. Corollary There exists a language L that is not Turing-recognizable. TMs and Problems Theorem The set of all Turing Machines is countable. Theorem The set of all languages is uncountable. Corollary There exists a language L that is not Turing-recognizable. Proof. If every language were T-recognizable, we can map every language to a TM that recognizes it; this would give a correspondence between an uncountable and a countable set. TMs and Problems Theorem The set of all Turing Machines is countable. Theorem The set of all languages is uncountable. Corollary There exists a language L that is not Turing-recognizable. Proof. If every language were T-recognizable, we can map every language to a TM that recognizes it; this would give a correspondence between an uncountable and a countable set. We have already seen some examples of undecidable languages (ATM ) and unrecognizable languages (ATM ). TMs and Problems Theorem The set of all Turing Machines is countable. Theorem The set of all languages is uncountable. Corollary There exists a language L that is not Turing-recognizable. Proof. If every language were T-recognizable, we can map every language to a TM that recognizes it; this would give a correspondence between an uncountable and a countable set. We have already seen some examples of undecidable languages (ATM ) and unrecognizable languages (ATM ). We next discuss techniques to show other problems are undecidable (and later unrecognizable).