Course syllabus - Formal Languages, Automata and Theory of Computation
Scope
7.5 credits
Course code
DVA337
Valid from
Autumn semester 2015
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
Literature lists
Course literature is preliminary up to 8 weeks before course start. Course literature can be valid over several semesters.
-
Books
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
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
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 students will be able to:
1. show the basic theoretical knowledge, which means be able to explain and apply concepts, structures, theoretical frameworks and tools and understand their inherent relationships. In particular, they will be able to construct and interpret the function of machines and explain the relationship between automata and languages,
2. apply practical knowledge, which is the ability to solve problems and demonstrate derivations and simulations of theoretical machines and grammars and also
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.
Computating paradigms.
Tuition
Teaching consists of lectures, exercises, labs and a seminar.
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, marks Fail (U), 3, 4 or 5. Examines learning objectives 1 and 2.
Written assignment (INL1), A short essay which is presented and discussed in a seminar, 1.5 credits, marks Fail (U) or Pass (G). Examines learning objective 3.
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.
Grade
Pass with distinction, Pass with credit, Pass, Fail
Interim Regulations and Other Regulations
The course completely overlaps with CD5560, CDT314 and DVA325 Formal Languages, Automata and Theory of Computation 7,5 credits.