## CS431 | Theory of Automata

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.