Syllabus for |
|
| TMV027 - Finite automata theory and formal languages |
| |
| Syllabus adopted 2015-02-12 by Head of Programme (or corresponding) |
| Owner: TKITE |
|
|
7,5 Credits |
| Grading: TH - Five, Four, Three, Not passed |
| Education cycle: First-cycle |
|
Major subject: Mathematics
|
|
Department: 37 - COMPUTER SCIENCE AND ENGINEERING
|
Teaching language: English
Open for exchange students
| Course module |
|
Credit distribution |
|
Examination dates |
|
Sp1 |
Sp2 |
Sp3 |
Sp4 |
Summer course |
No Sp |
| 0112 |
Examination |
6,0 c |
Grading: TH |
|
|
|
|
6,0 c
|
|
|
|
01 Jun 2016 pm M, |
17 Aug 2016 am SB |
| 0212 |
Written and oral assignments |
1,5 c |
Grading: UG |
|
|
|
|
1,5 c
|
|
|
|
|
In programs
TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
TKITE SOFTWARE ENGINEERING, Year 2 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (compulsory elective)
Examiner:
Docent
Ana Bove
Replaces
TMV025
Finite automata theory and formal languages TMV026
Finite automata theory and formal languages
Go to Course Homepage
Eligibility:
In order to be eligible for a first cycle course the applicant needs to fulfil the general and specific entry requirements of the programme(s) that has the course included in the study programme.
Course specific prerequisites
Knowledge in Discrete mathematics and in programming.
Aim
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'.
Learning outcomes (after completion of the course the student should be able to)
Knowledge and understanding
- Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, (non-)deterministic automata, regular expressions, regular languages, context-free grammars, context-free languages, Turing machines;
- Explain the power and the limitations of regular languages and context-free languages.
Skills and abilities
- Prove properties of languages, grammars and automata with rigorously formal mathematical methods;
- Design automata, regular expressions and context-free grammars accepting or generating a certain language;
- Describe the language accepted by an automaton or generated by a regular expression or a context-free grammar;
- Transform between equivalent deterministic and non-deterministic finite automata, and regular expressions;
- Simplify automata and context-free grammars;
- Determine if a certain word belongs to a language;
- Define Turing machines performing simple tasks.
Judgement and approach
- Differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions.
Content
The first 8 chapters of "Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman.
Formal proofs. Finite automata, regular expressions, and algorithms connecting the two notions. Context-free grammars. Pumping lemma and properties of regular and context-free languages. Short introduction to push-down automata and Turing machines.
Organisation
Lectures, exercise and consultation classes and weekly individual written assignments. If necessary lab sessions will be included.
Literature
"Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman, third edition.
Examination
The course is examined by individual weekly assignments during the course and an individual written exam given in an examination hall at the end of the course.
The final degree of the course is based on the performance of both the weekly assignments and the exam.