COURSE SYLLABUS

Formal Languages and Theory of Computation 7.5 Credits

Formella språk och beräkningsteori
Second cycle, D7006E
Version
Course syllabus valid: Autumn 2015 Sp 1 - Present
The version indicates the term and period for which this course syllabus is valid. The most recent version of the course syllabus is shown first.

Syllabus established
by the Department of Computer Science and Electrical Engineering 28 Feb 2007

Last revised
by Jonny Johansson, HUL SRT 12 Jun 2015

Education level
Second cycle
Grade scale
G U 3 4 5
Subject
Computer Science
Subject group (SCB)
Computer Technology

Entry requirements

Basic knowledge in mathematics equivalent to M0031M and a basic discrete mathematics course, equivalent to M0009M.


More information about English language requirements


Selection

The selection is based on 20-285 credits



Course Aim
The aim of the course is to given an introduction to and fundamental theories about computation and about different models of computation.

Contents
Deterministic and non-deterministic finite automata, regular expressions and languages, context-free languages and grammars, pushdown automata, Turing machines, undecidability and undecidable problems.

Realization
Lectures. During the course there could be homework assignments that render bonus points on the written exam that follows directly after the course has been given.

Examination
Written exam.

Remarks
The credits for this course cannot be combined with the credits for MAM205.

Examiner
Jingsen Chen

Transition terms
The course D7006E is equal to SMD177

Literature. Valid from Autumn 2007 Sp 1 (May change until 10 weeks before course start)
Michael Sipser, \"Introduction to the Theory of Computation\", 2nd Edition, Thomson, Boston, 2006, ISBN: 0-619-21764-2.

Course offered by
Department of Computer Science, Electrical and Space Engineering

Items/credits
NumberTypeCreditsGrade
0001Written exam7.5G U 3 4 5

Study guidance
Study guidance for the course is to be found in our learning platform Canvas before the course starts. Students applying for single subject courses get more information in the Welcome letter. You will find the learning platform via My LTU.