Formal Languages and Automata

SaToSS home

• Automata & Formal Languages
• Distributed Systems
• Formal Methods
• Game Theory
• Information Security Basics
• Introduction to IT Security
• Network Security
• Security Protocols
• Security Modeling

Information on the course Formal Languages and Automata is kept here. This course starts on 22 Feburary 2017 and is worth 3 ECTS points.

Instructors

• Prof. Dr. Sjouke Mauw
• Dr. Andrzej Mizera
• Dr. Yunior Ramírez Cruz

Objectives

To give the student an introduction to a mathematical framework for two central concepts in computer science: that of formal languages (e.g., such as programming languages) and that of computation. A study of formal languages and the correspondence between language classes and the automata that recognise them will be presented. Formal definitions of finite state automata and pushdown automata, deterministic and nondeterministic systems, context-free grammars and their ambiguity, finally Turing machines will be discussed.

Content

• Regular-languages
  • deterministic and nondeterministic finite automata
  • regular expressions
  • pumping lemma for regular languages
• Context-free languages
  • context-free grammars
  • pushdown automata
  • Chomsky normal form
  • pumping lemma for context-free languages
• Turing machines
  • formal definition of a Turing machine
  • Turing-recognisable and Turing-decidable languages
  • variants of Turing machines
  • definition of an algorithm

Reading material

The text book for this course is Michael Sipser's "Introduction to the Theory of Computation", Course Technology Inc, International edition, 2005.
ISBN-10: 0619217642
ISBN-13: 978-0619217648

Lecture notes are available via Moodle.

Moodle

Further information can be found on Moodle.