Theoretical Computer Science 1

Information on the course Theoretical Computer Science 1 (formerly Automata and Formal Languages) is kept here.



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.


Reading material

The text book for this course is Michael Sipser's "Introduction to the Theory of Computation", Cengage Learning, 3rd edition (EMEA), 2013.
ISBN-10: 113318779X
ISBN-13: 978-1133187790

Lecture notes are available via Moodle.


Further information can be found on Moodle.