Theory of Formal Languages (17-34-325)

Theory of Formal Languages (17-34-325)

List of Topics

• Regular Languages (DFAs, NFAs, Regular Expressions, Closure Properties, The Pumping Lemma, etc.)
• Context-Free Languages (CFGs, PDAs, Normal Forms, Ambiguity, Closure Properties, The Pumping Lemma, etc.)
• Turing Machines (TMs and LBAs, Context-Sensitive Languages, Chomsky Hierarchy, The Church-Turing Thesis, Variants of Turing Machines, etc.)
• An Introduction to Computability Theory (Decidability, Undecidability, Reducibility, etc.)
• A Brief Introduction to Complexity Theory (NP-completeness, Polynomial-Time Reducibility, The Cook-Levin Theorem, Karp's 21 Problems)

Textbooks

• Introduction to the Theory of Computation by Michael Sipser (3rd edition 2013)
• Introduction to Languages and the Theory of Computation by John C. Martin (4th edition 2011)
• An Introduction to Formal Languages and Automata by Peter Linz (6th edition 2017)