TDDA89 Formal Languages and Automata Theory, ECTS-points
/FORMELLA SPRÅK OCH AUTOMATATEORI/

Advancement level:
B

Aim:
The purpose of the course is to give an introduction to formal languages and automata theory.

Prerequisites:
TATM 43 Discrete mathematics, basic course, or TATM90 Discrete Mathematics and Logic or TDDB90 Discrete Mathematics and Logic

Course organization:
The theory is presented during the lectures. Problem solving is practiced during the lessons.

Course content:
Finite automata and regular expressions. Context-free grammars and pushdown automata. Deterministic context-free grammars, LR (0), LR (k). Chomsky's hierarchy. Orientation of Turing Machines and undecidability.

Course literature:
Hopcroft, Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979.

UPG 1Hand-in assignments
TEN 1Written examination
Course language is Swedish.