Search course

Use the search function to find more information about the study programmes and courses available at Chalmers. When there is a course homepage, a house symbol is shown that leads to this page.

Graduate courses

Departments' graduate courses for PhD-students.

​​​​
​​

Syllabus for

Academic year
TMV026 - Finite automata theory and formal languages
 
Syllabus adopted 2011-02-23 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

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0105 Examination 7,5 c Grading: TH   7,5 c   25 May 2012 am V,  31 Aug 2012 am M

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

Course evaluation:

http://document.chalmers.se/doc/00000000-0000-0000-0000-00003C873D72


  Go to Course Homepage

Eligibility:

For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.

Course specific prerequisites

Knowledge in mathematics, including a course in Discrete mathematics, and in programming.

Aim

This course presents both the theory of finite automata and of pushdown automata. It also includes a short introduction to Turing machines.

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

Pushdown automata are finite automata with stacks. The theory is more complex, but has important applications in parsing and analysis of context-free languages which is also a fundamental concept in computer science.

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)


  • Apply rigorously formal mathematical methods to prove properties of languages, grammars and automata.
  • Understand the theory and principle of automata theory.
  • Understand, differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions.
  • Use and define automata, regular expressions and context-free grammars to solve problems.

Content

The first 8 chapters of "Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman.

Formal proofs. Finite automata, regular expressions, algorithms connecting the two notions, pumping lemma for regular languages and properties of regular languages. Context-free grammar, eventually also push-down automata, and properties of context-free languages. If time allows the course will contain a short introduction to Turing machines.

Organisation

Lectures and exercise classes each week. Eventually lab sessions will be included if needed.

Literature

"Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman.

Examination

Written exam at the end of the course. Regular assignments might also be included as part of the examination.


Page manager Published: Thu 04 Feb 2021.