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
TMV028 - Finite automata and formal languages
Ändliga automater och formella språk
 
Syllabus adopted 2019-02-21 by Head of Programme (or corresponding)
Owner: TKITE
7,5 Credits
Grading: TH - Pass with distinction (5), Pass with credit (4), Pass (3), Fail
Education cycle: First-cycle
Major subject: Mathematics
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: English
Application code: 52112
Open for exchange students: Yes
Only students with the course round in the programme plan

Module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0119 Examination 6,0c Grading: TH   6,0c   18 Mar 2021 pm J,  18 Aug 2021 am J
0219 Written and oral assignments 1,5c Grading: UG   1,5c    

In programs

TKITE SOFTWARE ENGINEERING, Year 2 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)
TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)

Examiner:

Nils Anders Danielsson

  Go to Course Homepage


Eligibility

General entry requirements for bachelor's level (first cycle)
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.

Specific entry requirements

The same as for the programme that owns the course.
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.

Course specific prerequisites

Knowledge of discrete mathematics and programming.

Aim

The course's main topics are finite automata, regular expressions and context-free grammars. It also contains a short introduction to Turing machines.

Learning outcomes (after completion of the course the student should be able to)

Knowledge and understanding:

  • Define different concepts in automata theory and the theory of formal languages, such as (non-) deterministic automaton, regular expression, regular language, context-free grammar, context-free language, and Turing machine.
Competence and skills:
  • Prove properties of (some) languages, grammars and automata using rigorous mathematical methods.
  • Construct finite automata, regular expressions and context-free grammars accepting or generating certain languages.
  • Describe the language accepted by a finite automaton or generated by a regular expression or context-free grammar.
  • Convert descriptions of regular languages between the following formalisms: deterministic and non-deterministic finite automata as well as regular expressions.
  • Simplify automata and context-free grammars.
  • Determine if a word belongs to a certain (regular or context-free) language.
  • Construct Turing machines for simple tasks.
Judgement and approach:
  • Manipulate formal descriptions of (some) languages, grammars and automata.

Content

Finite automata and regular expressions are simple models of computation. They are for instance used to control traffic lights, to search for patterns, and for lexical analysis. Furthermore their theory can illustrate basic concepts in set theory and the theory of discrete structures.

Context-free grammars are used to parse and analyse both artificial languages (for instance programming languages) and natural languages.

Turing machines provide a more expressive model of computation. They help computer scientists understand the limits of mechanical computation by providing a precise definition of the concept of "algorithm".

More detailed contents: Proofs. Finite automata, regular expressions, and related algorithms. Context-free grammars. Properties of regular and context-free languages. A short introduction to Turing machines.

Organisation

Lectures, exercise sessions.

Literature

Course literature will be announced no later than 8 weeks prior to the start of the course.

Examination including compulsory elements

The course is examined by individual assignments and an individual written exam given in an examination hall.


Page manager Published: Thu 04 Feb 2021.