Text

Course syllabus - Formal Languages, Automata and Theory of Computation

Scope

7.5 credits

Course code

DVA337

Valid from

Autumn semester 2020

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

School

School of Innovation, Design and Engineering

Ratified

2014-06-24

Revised

2020-01-24

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: 2020-06-29

    Books

    Linz, Peter

    An introduction to formal languages and automata

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

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

    Mandatory

    Salling, Lennart

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

    [Ny utg.] : [Uppsala : Lennart Salling], cop. 1998 - 264 s.

    ISBN: 91-630-7707-8 LIBRIS-ID: 7453571

    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.

Tuition

Teaching consists of lectures, exercises and laborations.

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 a disability has the opportunity to submit a request for supportive measures during written examinations or other forms of examination, in accordance with the Rules and Regulations for Examinations at First-cycle and Second-cycle Level at Mälardalen University (2020/1655). It is the examiner who takes decisions on any supportive measures, based on what kind of certificate is issued, and in that case which measures are to be applied.

Suspicions of attempting to deceive in examinations (cheating) are reported to the Vice-Chancellor, in accordance with the Higher Education Ordinance, and are examined by the University’s Disciplinary Board. If the Disciplinary Board considers the student to be guilty of a disciplinary offence, the Board will take a decision on disciplinary action, which will be a warning or suspension.

Study guide

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.