Course Content and Course Plans

Content

This course presents both the theory of finite automata, regular expressions and context-free grammars. It also includes a short introduction to Turing machines.

Finite automata and regular expressions are one of the first and simplest models of computations. Their mathematical theory is quite elegant and simple. Finite automata are widely used in applications (traffic light, lexical analysis, pattern search algorithm, etc...), and constitute a perfect illustration of basic concepts in set theory and discrete structure.

Context-free grammars have important applications in parsing and analysis of both programming and natural language.

Turing machines were described by Alan Turing in 1937 and they are a powerful model of computation since they help computer scientists understand the limits of mechanical computation by providing a precise definition of an 'algorithm' or 'mechanical procedure'.

Course Plans

At Chalmers: link to TMV027 in the studieportalen.
At GU: Pdf with the description of DIT321.