Text

Course syllabus - Formal Languages, Automata and Theory of Computation

Scope

7.5 credits

Course code

DVA337

Valid from

Autumn semester 2026

Education level

First cycle

Progressive Specialisation

G2F (First cycle, has at least 60 credits in first-cycle course/s as entry requirements)

Main area(s)

Computer Science

Organisation

Department of Computer Science & Engineering

Ratified

2014-06-24

Revised

2025-11-03

Literature lists

Course literature is preliminary up to 8 weeks before course start. Course literature can be valid over several semesters.

    • Ratified date: 2020-06-29
    • Latest update: 2025-05-27

    Books

    Linz, Peter

    An introduction to formal languages and automata

    ISBN: 978-1-4496-3739-2 (hft.)

    LIBRIS-ID: 12418450

    5th ed., Sudbury, MA, Jones & Bartlett Learning, xiii, 437 p.

    Mandatory

    Salling, Lennart

    En introduktion till formella språk, automater och beräkningar

    ISBN: 91-630-7707-8

    LIBRIS-ID: 7453571

    [Ny utg.], [Uppsala, Lennart Salling], 264 s.

    Mandatory

    OBS! Endast en av ovanstående titlar behöver användas.

    Akademin för innovation, design och teknik,

Objectives

The course provides an insight into theoretical foundations of artificial languages, automata and theory of computation - topics that are ubiquitous in computer science.

Learning outcomes

After completing the course the student shall be able to:

  1. show basic theoretical knowledge, both regarding the connection between grammars, automata and languages and regarding fundamental limitations of computation,
  2. apply practical knowledge, both the ability to construct and simulate formal machines and grammars, and
  3. demonstrate the ability to reflect in writing on the course content in relation to different computational paradigms.

Course content

Regular languages and Finite automata.
Context-free languages and Pushdown automata.
Recursively enumerable languages and Turing machines.
The Universal Turing machine.
Decidability - Stop problem.
Computing paradigms.

Specific requirements

Theoretical knowledge and practical competence in a high level programming language and fundamentals of Discrete Mathematics or equivalent.

Examination

Examination (TEN1), written examination, 6 credits, examines the learning objectives 1 and 2, marks Fail (U), 3, 4 or 5.
Written assignment (INL1), a short essay, 1.5 credits, examines the learning objective 3, marks Fail (U) or Pass (G).

A student who has a certificate from MDU regarding disability study support, can request adaptions for the examination. It is the examiner who takes decisions on any adaptions, based on the certificate and other conditions.

Grade

Grading scale: 5, 4, 3

Interim Regulations and Other Regulations

The course completely overlaps with CD5560, CDT314 and DVA325 Formal Languages, Automata and Theory of Computation 7,5 credits.