Course Info

The course introduces advance concepts in automata theory and formal languages including grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine.

Finite automata, including the deterministic and nondeterministic versions | Regular expressions, their equivalence to finite automata, properties of the languages defined by regular expressions and finite automata | Context-free grammars and languages | Pushdown automata, their equivalence to context-free grammars, properties of context-free languages, introduction to Turing machines | Turing machines, decidability, undecidable problems | The classes P and NP, NP-complete problems

---

Course Aim

• Finite automata, including the deterministic and nondeterministic versions
• Regular expressions, their equivalence to finite automata, properties of the languages defined by regular expressions and finite automata
• Context-free grammars and languages
• Pushdown automata, their equivalence to context-free grammars, properties of context-free languages, introduction to Turing machines
• Turing machines, decidability, undecidable problems
• The classes P and NP, NP-complete problems

---

Learning Outcomes

• Learn how to deal formally with discrete systems
• Improve skills at proving facts, especially inductive proofs
• Understanding inductive proofs to formulate a reason why a method works
• Gain experience with abstract models and constructions
• Learn the process of simulation across models as the modern approach to programming in layered abstractions