Final Exam Topic Guide
This document summarizes all topics we¡¯ve covered in class. Topics are tagged with relevant HW problems and textbook sections.
Lecture 1.
¡ñ Proof that the real numbers are not countable. (Sipser 4.2)
¡ñ Definition of alphabets, strings, and languages. (Sipser 0.2)
¡ñ Definition of DFA, DFA state diagram, DFA acceptance and regular languages. (Sipser 1.1; HW
1, Problems 1 and 4)
Lecture 2.
¡ñ Definition of union, concatenation, and star. (Sipser 1.1)
¡ñ Proof that regular languages are closed under union (using DFAs.) (Sipser 1.1; HW 1, Problem 3)
¡ñ Definition of NFA, NFA state diagram and NFA acceptance. (Sipser 1.2; HW 1, Problem 2)
¡ñ Converting NFAs to DFAs. (Sipser 1.2; HW 2, Problem 2)
Lecture 3.
¡ñ Proof that the regular languages are closed under union, concatenation, and star using NFAs. (Sipser 1.2; HW 2, Problem 3)
¡ñ (Inductive) definition of regular expressions. (Sipser 1.3; HW 2, Problem 1)
¡ñ Proof that all regular expressions generate regular languages by conversion to NFA. (Sipser 1.3;
HW 2, Problem 2)
Lecture 4.
¡ñ Proof that all regular languages are generated by some regular expression by converting from DFA to GNFA to regular expressions. (Sipser 1.3; HW 3, Problem 3)
¡ñ Proof of the pumping lemma for regular languages. (Sipser 1.4) Lecture 5.
¡ñ Examples of using the pumping lemma to show that languages are nonregular. (Sipser 1.4; HW 3, Problem 1.2; HW 4, Problem 3.2)
¡ñ Example of using closure properties to show a language is nonregular. (Sipser 1.4; HW 3, Problem 1.1)
¡ñ Definition of context-free grammars and definition of context-free languages. (Sipser 2.1; HW 3, Problem 4; HW 4, Problems 1.1, 2.1 and 3.1)
¡ñ Building context-free grammars (Sipser 2.1; HW 3, Problems 4.3 and 4.4, HW 4, Problem 4)
¡ñ Parse trees, ambiguity and (leftmost) derivations. (Sipser 2.1; HW 4, Problem 1) Lecture 6.
¡ñ Chomsky Normal Form. (Sipser 2.1)
¡ñ Definition of PDA, PDA state diagrams, PDA acceptance. (Sipser 2.2) Lecture 7.
¡ñ PDA Examples. (Sipser 2.2)
¡ñ Proof that every CFL is recognized by some PDA by showing how to convert any CFG into a
PDA that nondeterministically tries every derivation to see if one generates the input string. (Sipser 2.2; HW 4, Problem 2.2)
¡ñ Sketched a proof that every language recognized by a PDA is context-free by creating a grammar in which each variable generates all strings that correspond to a sequence of transitions between two states in the PDA with empty stacks at either end. (Sipser 2.2)
¡ñ Introduced the pumping lemma for context-free languages. (Sipser 2.3) Lecture 8.
¡ñ Proof of the pumping lemma for context-free languages, some examples. (Sipser 2.3; HW 5, Problem 1)
¡ñ Defined TMs (formally), TM state diagrams and TM acceptance. Defined Turing-recognizable and Turing-decidable languages. (Sipser 3.1; HW 5, Problems 2, 3, 4.1, 4.2, and 4.3)
Lecture 9.
¡ñ Introduced Multitape TMs. Proof that they are equivalent to single-tape TMs Introduced nondeterministic TMs. Proof that they are equivalent to deterministic TMs. (Sipser 3.2; Equivalent models: HW 7, Problem 1)
¡ñ Introduced enumerators. Proof that a language is Turing-recognizable if and only if some enumerator enumerates it. (Sipser 3.2; HW 5, Problem 4.4)
¡ñ Distinguished formal descriptions from implementation-level and high-level descriptions. (Sipser 3.3; HW 5, Problems 2 and 3)
¡ñ Introduced the Church-Turing thesis: a precisely-specified process, or algorithm, is precisely captured by what a TM can do. (Sipser 3.3)
Lecture 10.
¡ñ Proof that A_{DFA}, A_{NFA}, A_{REX}, E_{DFA}, and EQ_{DFA} are decidable. Stated that A_{CFG}, E_{CFG}, and EQ_{CFG} are decidable. Built some deciders directly, used others as subroutines and exploited closure properties. (Sipser 4.1; HW 7, Problem 2.1 and 2.2)
¡ñ Proof that the context-free languages are Turing-decidable. (Sipser 4.1)
¡ñ Defined countable and uncountable sets. (Sipser 4.2)
¡ñ Proof that the set of TMs is countable and the set of infinite binary strings is uncountable. Used
this to show that some languages must not be Turing-recognizable. (Sipser 4.2)
¡ñ Proof that A_{TM} is not Turing-decidable using a ¡®paradox machine¡¯ and, after defining
co-Turing-recognizability, proof that the complement of A_{TM} is not Turing-recognizable.
(Sipser 4.3)
Lecture 11.
¡ñ Introduced the notion of Turing-reductions to show languages are undecidable. (Sipser 5.1; HW 7, Problem 3)
¡ñ Reviewed Big-O notation and defined time complexity. (Sipser 7.1)
¡ñ Defined the time complexity classes P and NP. (Sipser 7.2, 7.3)