everything.study
MATH 4805

Theory of Automata (Honours)

0.5 credit · Undergraduate

Finite automata and regular expressions, properties of regular sets, context-free grammars, pushdown automata, deterministic context-free languages. Turing machines, the Chomsky hierarchy. Undecidability, intractable problems.

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 listed as COMP 4805 . Prerequisite(s): MATH 3106 or MATH 3158 or MATH 3855 or permission of the School. Also offered at the graduate level, with different requirements, as MATH 5605 , for which additional credit is precluded. Lectures three hours a week.

Sources