Automata Theory

Study of abstract machines and computational models

Automata Theory#

Automata theory is the study of abstract machines and computational models. It provides a theoretical foundation for understanding computation and formal languages.

Topics#

  • Deterministic Finite Automata
  • Non-Deterministic Finite Automata
  • Regular Languages
  • Pumping Lemma for Regular Languages
  • Context Free Grammars
  • Pushdown Automata
  • Turing Machines
  • Church-Turing Thesis
  • Turing-Completeness
  • Incompleteness and Undecidability

Resources#

Books#

  • Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  • Elements of the Theory of Computation by Harry R. Lewis, Christos H. Papadimitriou
  • Automata and Computability by Dexter C. Kozen
  • Theory of Computation by Michael Sipser

Online Resources#

Practice Problems#