INHN0013 Information Theory & Theory of Computation Lecture Notes PDF

Welcome INHN0013 Information Theory & Theory of Computation Stephen Kobourov Prof. of Computer Science Theory of Computation Computability: what problems cannot be solved: Hilbert was wrong? for solvable problems, how power...

Welcome INHN0013 Information Theory & Theory of Computation Stephen Kobourov Prof. of Computer Science Theory of Computation Computability: what problems cannot be solved: Hilbert was wrong? for solvable problems, how powerful a machine do we need? what computation models are there? Theory of Computation Computability: what problems cannot be solved: Hilbert was wrong? for solvable problems, how powerful a machine do we need? what computation models are there? Complexity: the big divide: the classes P and NP ($1M) NP-completeness and reductions approximation/randomized algorithms Famous and Important Results Everyone Should Know Chomsky’s Language Hierarchy The Church-Turing thesis Der Entscheidungsproblem Gödel’s Incompleteness Theorems The Cook-Levin Theorem Cantor’s Infinities Textbook and Other Reading Edition: 2nd or 3rd e-book available through the TUM library Class Format Lectures, Mondays, 9:30-11:45pm Exercises, 90 minutes every week Two Midterm exams Comprehensive final exam Moodle page: more info, lecture notes, exercise sheets, etc. Reading: Chapters 0 and 1 Automata, Grammars, and Languages This course introduces the fundamental models of computation used throughout computer science: finite automata, pushdown automata, and Turing machines. We will investigate the limitations of computation: what can and what cannot be computed, and what can be computed using a realistic amount of resources. We will study computational complexity, complexity classes, relationships among complexity classes, NP-hardness and NP-completeness. The course stresses methods for formal reasoning and modeling of general computation. This is a theory class and there will be no programming. The key techniques to be learned are those of simulation of one computational model by another, reduction of one problem to another, and methods for classifying problem complexity. Course Syllabus Chapter 0 (Review): Mathematical Notation and Terminology, Definitions, Theorems, and Proofs, Types of Proofs Chapter 1. Regular Languages: 1.1: DFAs, 1.2: NFAs, 1.3: Regular Expressions, 1.4: Non-regular languages Chapter 2. Context-Free (CF) Languages : 2.1: CF Grammars, 2.2: Pushdown Automata, 2.3: Non-CF Languages Chapter 3. Church-Turing Thesis: 3.1: Turing Machines, 3.2: Turing Machine Variants, 3.3: The Definition of Algorithm Chapter 4. Decidability: 4.1: Decidable Languages, 4.2: Undecidability and The Halting Problem Chapter 5. Reducibility: 5.1: Undecidable Problems, 5.2: More Undecidable Problems Chapter 7. Time Complexity: 7.1: Measuring Complexity, 7.2, 7.3: The P and NP Classes, 7.4: NP-completeness Chapter 8: Space Complexity: 8.1: Savitch’s Theorem, 8.2: PSPACE Course Participation and Learning Environment Actively participating in the course, attending lectures and exercises, asking and answering questions on moodle are vital to the learning process; absences will very likely a↵ect a student’s performance. TUM is committed to providing and maintaining a supportive educational environment for all. We strive to be welcoming and inclusive, respect privacy and confidentiality, behave respectfully and courteously, and practice intellectual honesty. Disruptive behaviors (such as physical or emotional harassment, dismissive attitudes, and abuse of department resources) will not be tolerated. To foster a positive learning environment, students and instructors have a shared responsibility. To that end, our focus is on the tasks at hand and not on extraneous activities (e.g., texting, chatting, making phone calls, web surfing, etc.). Grading The two midterm exams during the semester are optional, but highly recommended. Each 60-minute midterm exam will show you the type of questions likely to appear on the final exam and also how such questions are graded. By achieving at least 50% of the total number of points for each midterm exam you will obtain a grade bonus of 0.3 that applies if you pass the final exam. To obtain a passing grade on the final exam you also need at least 50% of the total number of points. Moodle has more and more detailed information. Automata, Grammars, and Languages Recall that Theory of Computation deals with two majors aspects: computability and complexity Computability: What are the fundamental capabilities and limitations of computers? Complexity: What makes some problems computationally hard and others easy? Automata, Grammars, and Languages Automata (machines) come in di↵erent strengths, depending on their ability to remember stu↵ (memory) and on the way to look up stu↵ (access) Automata can be seen as processing strings over some alphabet (e.g., binary) and either accept or reject each valid string The language of an automaton is the set of strings it accepts A grammar is made of rules that generate all strings in a given language For now computation simply means determining whether a given string is in the language or not (decision problem) The Simplest Computational Model: Finite Automata A finite automaton is a 5-tuple (Q, ⌃, , qs , F ), where Q is a finite set called the states, ⌃ is a finite set called the alphabet, : Q ⇥ ⌃ ! Q is the transition function, qs 2 Q is the start state, F ✓ Q is the set of accept states. Finite Automata This particular finite automaton is given by the 5-tuple (Q, ⌃, , qs , F ), where Q= ⌃= is: start state is: accepts states are: Finite Automata What does this machine M do? Finite Automata What does this machine M do? The set of all strings that M accepts is the language of the machine, L(M). Finite Automata What does this machine M do? The set of all strings that M accepts is the language of the machine, L(M). A = {w |w contains at least one 1 and an even number of 0s follow the last 1}. Computation of a Finite Automaton Let M = (Q, ⌃, , qS , F ) be a finite automaton and let w = w1 w2... wn be a string where each wi is a member of the alphabet ⌃. Then M accepts w if a sequence of states r0 , r1 ,... , rn in Q exists with three conditions: r0 = qS , (ri , wi+1 ) = ri+1 , for i = 0,..., n 1, rn 2 F. Computation of a Finite Automaton Let M = (Q, ⌃, , qS , F ) be a finite automaton and let w = w1 w2... wn be a string where each wi is a member of the alphabet ⌃. Then M accepts w if a sequence of states r0 , r1 ,... , rn in Q exists with three conditions: r0 = qS , (ri , wi+1 ) = ri+1 , for i = 0,..., n 1, rn 2 F. About automaton computation: A machine may accept several strings, but it always recognizes only one language. Computation of a Finite Automaton Let M = (Q, ⌃, , qS , F ) be a finite automaton and let w = w1 w2... wn be a string where each wi is a member of the alphabet ⌃. Then M accepts w if a sequence of states r0 , r1 ,... , rn in Q exists with three conditions: r0 = qS , (ri , wi+1 ) = ri+1 , for i = 0,..., n 1, rn 2 F. About automaton computation: A machine may accept several strings, but it always recognizes only one language. If the machine accepts no strings, it still recognizes one language, the empty language ;. Designing Automata Let’s design an automaton that recognizes strings with an odd number of 1s, over the alphabet {0, 1}. Designing Automata Let’s design an automaton that recognizes strings with an odd number of 1s, over the alphabet {0, 1}. do we need to count the number of 1s in the string? Designing Automata Let’s design an automaton that recognizes strings with an odd number of 1s, over the alphabet {0, 1}. do we need to count the number of 1s in the string? just keep track whether the number so far is odd or even Designing Automata Let’s design an automaton that recognizes strings with an odd number of 1s, over the alphabet {0, 1}. do we need to count the number of 1s in the string? just keep track whether the number so far is odd or even we can do this with just two states Designing Automata Let’s design an automaton that recognizes strings with an odd number of 1s, over the alphabet {0, 1}. do we need to count the number of 1s in the string? just keep track whether the number so far is odd or even we can do this with just two states Designing Automata Let’s design an automaton that recognizes strings that contain 001 as a substring, again over the alphabet {0, 1}. Designing Automata Let’s design an automaton that recognizes strings that contain 001 as a substring, again over the alphabet {0, 1}. Regular Operations A language is called a regular language if some finite automaton recognizes it. Regular Operations A language is called a regular language if some finite automaton recognizes it. Let A and B be languages. We define the regular operations union, concatenation, and star as follows: Union: A [ B = {x|x 2 A or x 2 B}. Concatenation: A B = {xy |x 2 A and y 2 B}. Star: A⇤ = {x1 x2... xk |k 0 and each xi 2 A}. There are two special characters: ✏: the empty string ;: the empty language Example of Regular Operations Let the alphabet ⌃ be the standard 26 letters {a, b,... , z}. Example of Regular Operations Let the alphabet ⌃ be the standard 26 letters {a, b,... , z}. If A = {good, bad} and B = {boy , girl}, then Example of Regular Operations Let the alphabet ⌃ be the standard 26 letters {a, b,... , z}. If A = {good, bad} and B = {boy , girl}, then A [ B = {good, bad, boy , girl} Example of Regular Operations Let the alphabet ⌃ be the standard 26 letters {a, b,... , z}. If A = {good, bad} and B = {boy , girl}, then A [ B = {good, bad, boy , girl} A B = {goodboy , goodgirl, badboy , badgirl} Example of Regular Operations Let the alphabet ⌃ be the standard 26 letters {a, b,... , z}. If A = {good, bad} and B = {boy , girl}, then A [ B = {good, bad, boy , girl} A B = {goodboy , goodgirl, badboy , badgirl} A⇤ = {✏, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood,...} Properties of Regular Languages Theorem The class of regular languages is closed under the union operation. Properties of Regular Languages Theorem The class of regular languages is closed under the union operation. What does “closed under union” mean? “If languages A1 and A2 are regular, then their union A1 [ A2 is also regular.” For example, the class of integers is closed under addition and multiplication (but not under division). Properties of Regular Languages Theorem The class of regular languages is closed under the union operation. Proof. Given two regular languages A1 and A2 we want to show that A1 [ A2 also is regular. Let M1 be a finite automaton for A1 and M2 be a finite automaton for A2. To prove that A1 [ A2 is regular, we construct a finite automaton M that recognizes A1 [ A2 , using M1 and M2 as building blocks. M works by simultaneously simulating M1 and M2 and accepting if either of the simulations accept. M can keep track of the simulations by using as many states as the product of the states in M1 and M2. Closure under Union Example Closure under Union: Detailed Proof Proof. Let M1 recognize A1 , where M1 = (Q1 , ⌃, 1 , q1 , F1 ), and M2 recognize A2 , where M2 = (Q2 , ⌃, 2 , q2 , F2 ). Construct M to recognize A1 [ A2 , where M = (Q, ⌃, , q0 , F ). 1 Q = {(r1 , r2 )|r1 2 Q1 and r2 2 Q2 }. Q is the Cartesian product of the sets Q1 ⇥ Q2. 2 ⌃ is the alphabet of M1 and M2. Theorem is true if alphabets are di↵erent; then ⌃ = ⌃1 [ ⌃2. 3 ((r1 , r2 ), a) = ( 1 (r1 , a), 2 (r2 , a)), for each (r1 , r2 ) 2 Q and each a 2 ⌃ 4 q0 is the pair (q1 , q2 ). 5 F = {(r1 , r2 )|r1 2 F1 or r2 2 F2 }. Nondeterministic Finite Automata A finite automaton is a 5-tuple (Q, ⌃, , qs , F ), where Q is a finite set called the states, ⌃ is a finite set called the alphabet, : Q ⇥ ⌃✏ ! P(Q) is the transition function, qs 2 Q is the start state, F ✓ Q is the set of accept states. NFAs Nondeterminism is a generalization of determinism, so every deterministic finite automaton (DFA) is automatically a nondeterministic finite automaton (NFA). Every state of a DFA always has exactly one exiting transition arrow for each symbol in the alphabet. In an NFA, a state may have zero, one, or many exiting arrows for each alphabet symbol. In a DFA, labels on the transition arrows are symbols from the alphabet. In general, an NFA may have arrows labeled with members of the alphabet or ✏. Zero, one, or many arrows may exit from each state with the label ✏. NFA Computation Suppose an NFA runs on an input string and comes to a state with multiple ways to proceed on the same symbol. After reading that symbol, the machine splits into multiple copies of itself and follows all the possibilities in parallel. Each copy of the machine takes one of the possible ways to proceed and continues as before. If there are subsequent choices, the machine splits again. If the next input symbol doesn’t appear on any of the arrows exiting the state occupied by a copy of the machine, that copy of the machine dies, along with the branch of the computation associated with it. Finally, if any one of these copies of the machine is in an accept state at the end of the input, the NFA accepts the input string. NFA Computation NFA Computation Let N = (Q, ⌃, , qS , F ) be a finite automaton and let w = w1 w2... wn be a string where each wi is a member of the alphabet ⌃✏. Then N accepts w if a sequence of states r0 , r1 ,... , rn in Q exists with three conditions: r0 = qS , ri+1 2 (ri , wi+1 ), for i = 0,..., n 1, rn 2 F. An NFA accepts if any of its (possibly exponentially many) computation paths ends in an accept state. Are Nondeterministic FA More Powerful? What do we mean by powerful? the computational power of a machine is measured by the class of languages that it can recognize the computational power of a machine then is measured by the number of problems it can solve Are Nondeterministic FA More Powerful? What do we mean by powerful? the computational power of a machine is measured by the class of languages that it can recognize the computational power of a machine then is measured by the number of problems it can solve So, while it’s easier to design NFAs (they can be smaller and simpler), it turns out that NFAs recognize exactly the same class of languages as DFAs NFAs Theorem A language is regular if and only if some NFA recognizes it. Proof. ) Let L be a regular language. Then by definition there exists a DFA for L. Since a DFA is a special case of an NFA (an NFA without multiple transitions on the same symbol), we are done. NFAs Theorem A language is regular if and only if some NFA recognizes it. Proof. ) Let L be a regular language. Then by definition there exists a DFA for L. Since a DFA is a special case of an NFA (an NFA without multiple transitions on the same symbol), we are done. ( Let N be an NFA. We will show how to create an equivalent DFA M. Then L(N) = L(M) and by definition, this language is regular. NFA to DFA Example NFA to DFA Example Equivalence of NFAs and DFAs (cont.) Theorem Every NFA has an equivalent DFA Proof. Let N = (Q, ⌃, , qs , F ) be an NFA that recognizes language A. We will construct DFA M = (Q 0 , ⌃, 0 , qs0 , F 0 ) that recognizes A. Q 0 = P(Q) for R 2 Q 0 and a 2 ⌃ let 0 (R, a) = {q 2 Q|q 2 E ( (r , a)) for some r 2 R} qS0 = E (qs ) F 0 = {R 2 Q 0 |R contains an accept state of N} where E (R) = {q|q can be reached from R by traveling along 0 or more ✏ arrows. Closure under Union Theorem The class of regular languages is closed under the union operation. Proof. We proved this with DFAs; now we redo it with NFAs.