Search programme

​Use the search function to search amongst programmes at Chalmers. The programme overview and the programme syllabus relating to your studies are generally from the academic year you began your studies.

​​​

Syllabus for

 Academic year
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

TKITE SOFTWARE ENGINEERING, Year 2 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (compulsory elective)
TKDAT COMPUTER SCIENCE AND ENGINEERING, Year 3 (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.

Page manager Published: Thu 03 Nov 2022.