everything.study
MATH 5605

Theory of Automata

0.5 credit · Graduate

Algebraic structure of sequential machines, de-composition of machines; finite automata, formal languages; complexity.

2020

Topics

  • Introduction, language and operations.
  • Operations, machines, DFA.
  • Counting with automata; Recognizable languages.
  • Oct. 2 Classification of recognizable language with 1 input letter
  • NFA and applications.
  • Grammars; Right linear grammars
  • Applications of ε-NFA; Monoid homomorphism
  • Kleene’s theorem.
  • Follower sets and quotient automaton.
  • Algorithm to compute the minimal automaton. RM(n).
  • Homomorphism of monoids revisited. Syntact monoids.
  • Dec. 4 Push down automaton and context free language.
  • Pumping lemma; Automaton with output (transducers).

Readings

  • “An introduction to formal languages and automata” by Peter Linz.

Prerequisites & course information

Also offered at the undergraduate level, with different requirements, as MATH 4805 / COMP 4805 , for which additional credit is precluded.

Sources