CE 409 – Formal Languages and Automata

CE 409 – Formal Languages and Automata; Weekly hours: 2+0, ECTS: 4
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. Not only do they form basic models of computation, they are also the foundation of many branches of computer science, e.g. compilers, software engineering, concurrent systems, etc. The properties of these models will be studied and various rigorous techniques for analyzing and comparing them will be discussed, by using both formalism and examples. Course Contents: Introduction to Automata; Central concepts of automata theory; Finite automata; Deterministic finite automata; Regular expressions and languages; Context-free grammar and languages; Parse trees; Pushdown automata; Languages of pushdown automata; Deterministic pushdown automata; Introduction to Turing machines; Programming techniques for Turing machines.