Finite Automata
Deterministic Finite Automata (DFA).
Nondeterministic Finite Automata (NFA).
Equivalence of DFA and NFA.
Regular Languages and Expressions
Regular expressions.
Applications in text processing.
Pushdown Automata (PDA)
Relation to context-free grammars.
Parsing and syntax analysis.
Context-Free Languages
Chomsky hierarchy.
Applications in programming languages.
Turing Machines
Concept and components.
Variants of Turing machines.
Significance in computability.
Computability and Decidability
Church-Turing thesis.
Decidable and undecidable problems.
Lambda Calculus
Basics and relation to functional programming.
Expressions and reductions.
Applications of Automata Theory
Compiler design.
Protocol verification.