Problem Solving in Automata, Languages, and Complexity

[550/47%]

D. Du, K. Ko

Chapter 1Regular Languages[46/52%]

Section 1.1Strings and Languages[18/56%]

Section 1.2Regular Languages and Regular Expressions[20/60%]

Section 1.3Graph Representations for Regular Expressions[8/25%]

Chapter 2Finite Automata[102/59%]

Section 2.1Deterministic Finite Automata[8/63%]

Section 2.2Examples of Deterministic Finite Automata[13/77%]

Section 2.3Nondeterministic Finite Automata[10/60%]

Section 2.4Converting an NFA to a DFA[8/63%]

Section 2.5Finite Automata and Regular Expressions[7/43%]

Section 2.6Closure Properties of Regular Languages[22/50%]

Section 2.7Minimum Deterministic Finite Automata[14/64%]

Section 2.8Pumping Lemmas[20/55%]

Chapter 3Context-Free Languages[95/52%]

Section 3.1Context-Free Grammars[18/50%]

Section 3.2More Examples of Context-Free Grammars[14/64%]

Section 3.3Parsing and Ambiguity[13/38%]

Section 3.4Pushdown Automata[11/64%]

Section 3.5Pushdown Automata and Context-Free Grammars[13/46%]

Section 3.6Pumping Lemmas for Context-Free Languages[26/50%]

Chapter 4Turing Machines[89/37%]

Section 4.1One-Tape Turing Machines[7/14%]

Section 4.2Examples of Turing Machines[17/41%]

Section 4.3Multi-Tape Turing Machines[9/22%]

Section 4.4Church-Turing Thesis[1/0%]

Section 4.5Unrestricted Grammars[9/44%]

Section 4.6Primitive Recursive Functions[17/59%]

Section 4.7Pairing Functions and Gödel Numberings[18/33%]

Section 4.8Partial Recursive Functions[11/27%]

Chapter 5Computability Theory[90/36%]

Section 5.1Universal Turing Machines[6/50%]

Section 5.2R. E. Sets and Recursive Sets[15/33%]

Section 5.3Diagonalization[15/33%]

Section 5.4Reducibility[24/33%]

Section 5.5Recursion Theorem[18/28%]

Section 5.6Undecidable Problems[12/50%]

Chapter 6Computational Complexity[57/32%]

Section 6.1Asymptotic Growth Rate[12/33%]

Section 6.2Time and Space Complexity[13/38%]

Section 6.3Hierarchy Theorems[12/33%]

Section 6.4Nondeterministic Turing Machines[12/25%]

Section 6.5Context-Sensitive Languages[8/25%]

Chapter 7NP-Completeness[71/58%]

Section 7.1NP[23/65%]

Section 7.2Polynomial-Time Reducibility[13/62%]

Section 7.3Cook's Theorem[12/42%]

Section 7.4More NP-Complete Problems[12/58%]

Section 7.5NP-Complete Optimization Problems[11/55%]