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, 24 April 2013
- Responsible department
- Department of Mathematics
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 for automata and formal languages;
- 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.
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