This course covers two basic models of computation: finite
automata and pushdown automata. We will discuss the various
forms that these models can take, the equivalence or
inequivalence of each type of model, and the problems that
can or cannot be solved by each model.
The topics covered will include:
-
Introduction: Motivation, mathematical preliminaries.
-
Finite automata: Deterministic finite automata,
nondeterministic finite automata, regular expressions,
nonregular languages, algorithms for finite automata,
state minimization.
-
Context-free languages: Context-free grammars, pushdown
automata, languages and automata, languages that are not
context-free, determinism.
If we have time, I would like to cover some additional
topics, at least superficially (in order of decreasing
priority):
-
Using Regular Expression in programming.
-
Using Finite and Pushdown Automata in programming.
-
Applications: circuit design, embedded systems, user
interfaces, security, etc.
-
Automata for reactive systems: Mealy and Moore Machines,
UML Statecharts, Input/Output Automata, Process Algebras.
-
Other automata: Cellular Automata, Buchi Automata.
-
Advanced notions of equivalence of automata: testing,
bisimilarity.
-
Temporal logics.
