Subjects Taught

Back to Subjects

CS431 | Theory of Automata

Background - Automata Theory A Simple State Machine Download
Languages Define Language, Set Forming Notation, Kleen Star Download
Recursive Definition of Languages Multiple Examples of Recursive Languages Download
Regular Expression Descriptive Language vs RE Download
Finite Automata DFA, Transition Table, Applications Download
Transition Graphs Introduction to First NFA Theoretical Machine Download
Kleen's Theorem Non-Deterministic Finite Automata Download
Finite Automata with Output Moore and Mealy Machines Download
Regular Languages Complement of a Language Download
Non-Regular Languages The Pumping Lemma Download
Decidability Membership, Empty and Infinite Problems Download
Context Free Grammar Production and Derivation, Parse Trees Download
Grammatical Format CFL to RL, Unit and Null Productions, CNF Download
Push Down Automata PDA Language Download
CFG = PDA Constructive Algorithm Download
Non-Context-Free Languages Pumping Lemma for CFLs Download
Context-Free Languages Union, Concatenation, Kleen Star, Intersection Download
Decidability (CFLs) Membership, Emptiness and Finiteness Problems Download
Turing Machines Program Rules, The Halting Problem Download
JFLAP A Tool to develop Finite Automata Download
Theory of Automata

Introduction to Computer Theory 2nd Edition
By: Daniel I. Cohen

Course Info

The course introduces some fundamental concepts in automata theory and formal languages including grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine. The course deals with the concept of computability and mathematical models, such as finite automata, grammars and Turing machines, and the relations between these models. The following topics are treated: Automata: finite automata, stack automata and Turing machines. Determinism and non-determinism. Regular expressions, transformation from regular expressions to finite automata and conversely, minimization of deterministic finite automata. Formal languages: grammars, Chomsky’s hierarchy, context-free grammars and regular grammars, closure properties. The relation between grammars and variants of automata. The pumping lemmas for regular and context-free languages, respectively. The universal machine, the halting problem and other undecidable problems.

Presenting the theory of finite automata, as the first step towards learning advanced topics, such as compiler design. | Applying the concepts learned in fundamental courses such as Discrete Mathematics, in a theoretical setting; in particular, the application of proof techniques. | Discussing the applications of finite automata towards text processing. | Developing an understanding of computation through Turing Machines


Course Aim
  • Presenting the theory of finite automata, as the first step towards learning advanced topics, such as compiler design.
  • Applying the concepts learned in fundamental courses such as Discrete Mathematics, in a theoretical setting; in particular, the application of proof techniques.
  • Discussing the applications of finite automata towards text processing.
  • Developing an understanding of computation through Turing Machines

Learning Outcomes
  • Prove properties of languages, grammars and automata with rigorously formal mathematical methods.
  • Design automata, regular expressions and context-free grammars accepting or generating a certain language.
  • Describe the language accepted by an automaton or generated by a regular expression or a context-free grammar.
  • Transform between equivalent deterministic and non-deterministic finite automata, and regular expressions.
  • Simplify automata and context-free grammars.
  • Determine if a certain word belongs to a language.
  • Define Turing machines performing simple tasks.