Automata Theory
Syllabus, Bachelor's level, 1MA009
- Code
- 1MA009
- Education cycle
- First cycle
- Main field(s) of study and in-depth level
- Computer Science G1F, Mathematics G1F
- Grading system
- Pass with distinction (5), Pass with credit (4), Pass (3), Fail (U)
- Finalised by
- The Faculty Board of Science and Technology, 10 February 2020
- Responsible department
- Department of Mathematics
Entry requirements
Algebra I.
Learning outcomes
On completion of the course, the student should be able to:
- describe how finite automata, stacking machines, context-free grammars and Turing machines work;
- use finite automata, stacking machines, context-free grammars and Turing machines to solve problems;
- use algorithms specified in the course for i. e. the following purposes: conversion of a non-deterministic finite automaton to a deterministic one, conversion of a finite automaton into a regular expression and vice versa, and minimization of a deterministic finite automaton;
- describe and use Chomsky's language hierarchy including the terms regular language, context-free language, Turing decidable language and Turing acceptable language;
- in simpler cases, determine whether a language belongs to a particular language family (in Chomsky's language hierarchy) or not.
Content
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, minimisation of deterministic finite automata.
Formal languages: grammars, Chomsky's hierarchy, in particular 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, Rice's theorem.
Instruction
Lectures and problem solving sessions.
Assessment
Written examination combined oral and written assignments given during the course.
If there are special reasons for doing so, an examiner may make an exception from the method of assessment indicated and allow a student to be assessed by another method. An example of special reasons might be a certificate regarding special pedagogical support from the disability coordinator of the university.