Skip to main content
Breadcrumb

Finite automata and formal languages

Course
Bachelor’s level
7,5 credits (ECTS)
Study pace
50%
Time
Day
Location
Göteborg
Study form
Campus
Language
English
Duration
-
Application open
-
Application code
GU-28608
Tuition
Full education cost: 17 875 SEK
First payment: 17 875 SEK

About

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

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.

Prerequisites and selection

Requirements

To be eligible for this course, students must have successfully completed 45 credits in computer science or mathematics, including the following Courses:
7.5 credits in discrete mathematics (for example DIT980, MMG200 or equivalent)
7.5 credits in programming (for example DIT440, DIT143, DIT012, DIT948, DIT953, MVG200 or equivalent)

Selection

Selection is based upon the number of credits from previous university studies, maximum 225 credits.