For Better Performance Please Use Chrome or Firefox Web Browser

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)