Automata Theory

5 credits

Syllabus, Bachelor's level, 1MA009

A revised version of the syllabus is available.

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, 15 March 2007
Responsible department: Department of Mathematics

What is a course syllabus?

Entry requirements

Algebra I

Learning outcomes

In order to pass the course (grade 3) the student should be able to

give an account of important concepts and definitions in the area of the course;

exemplify and interpret important concepts in specific cases;

formulate important results and theorems covered by the course;

describe the main features of the proofs of important theorems;

express problems from relevant areas of applications in a mathematical form suitable for further analysis;

use the theory, methods and techniques of the course to solve mathematical problems;

present mathematical arguments to others.

Higher grades, 4 or 5, require a higher level of proficiency. The student should be able to solve problems of greater complexity, i.e. problems requiring a combination of ideas and methods for their solution, and be able to give a more detailed account of the proofs of important theorems and by examples and counter-examples be able to motivate the scope of various results. Requirements concerning the student's ability to present mathematical arguments and reasoning are greater.

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 at the end of the course. Moreover, compulsory assignments may be given during the course.