CloseHelpPrint
Kies de Nederlandse taal
Course module: 202001361
202001361
Languages & Machines
Course info
Course module202001361
Credits (ECTS)3.5
Course typeStudy Unit
Language of instructionEnglish
Contact persondr.ing. E.M. Hahn
E-maile.m.hahn@utwente.nl
Lecturer(s)
Contactperson for the course
dr.ing. E.M. Hahn
Examiner
dr.ing. E.M. Hahn
Lecturer
dr. B. Manthey
Examiner
dr. A. Skopalik
Examiner
prof.dr. M.J. Uetz
Academic year2021
Starting block
2A
RemarksMinor students: register for the minor!
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Aims
After following this study unit, the student
  • is able to describe formal languages with the means of automata (deterministic and nondeterministic finite automata, push-down automata, Turing machines) and grammars (regular expressions, context-free and unrestricted grammars).
  • can determine and prove whether a language is regular, context-free or recursive.
  • is able to systematically transform and manipulate automata or grammars (minimization, determinization, normal forms, product automata, acceptance conditions).
  • is able to formally prove statements using a basic toolbox of formal techniques (e.g. recursive definitions, mathematical induction, diagonalization).
Content
In the study unit “Languages and Machines” we study several types of grammars and automata models. Grammars are formalisms to describe formal languages which are finite descriptions of possibly infinite sets of words. We also study several automata models which allow for the mathematical study of computation which receives words as inputs and decides whether the input word belongs to a given formal language.

Formal languages are sets of words over a given alphabet that are formed due to a systematic description. Formal languages are used for example in translation projects for natural language, for searching and indexing texts, for specifying and verifying (safe) computer systems, for definition and analysis of programming languages, and for the analysis of the complexity of algorithms.

In the first part, we study regular languages and we show that there are equivalent ways to describe a regular language namely by deterministic or non-deterministic finite automata, regular expressions or regular grammars. We learn and prove how to systematically turn a specification by one model into an equivalent representation by another one. We show that there is a systematic way (pumping lemma) to prove that a language is not regular and, hence, cannot be described by any of the equivalent formalisms above.

In the second part, we study context-free languages which are a superset of the regular languages. They can be described by context-free grammars and pushdown automata (PDA). We show that these two formalisms are equally expressive. However, unlike finite automata, deterministic PDA are strictly less powerful. For grammars, we study the systematic transformation into normal forms and the algorithmic problem of deciding the membership of a word in the grammar specified by context-free grammar. We show that there are languages that are not context-free and that we can prove this for a given language by a pumping lemma.

In the last part, we study Turing machines which are a machine model that is (in principle) as expressive as modern computers. We prove the somewhat surprising result that, even for this model, there exist languages which a Turing machine cannot decide. We learn and prove that unrestricted grammars are equivalent to Turing machines.
Assumed previous knowledge
Self study: For the part Language and Machines the book Languages and Machines: An Introduction to the Theory of Computer Science, Thomas A. Sudkamp, 3rd ed., Addison-Wesley, 2005 may be unavailable to purchase. The following book can be chosen as alternative: Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed.)
Resources for self study
For the part Language and Machines the book Languages and Machines: An Introduction to the Theory of Computer Science, Thomas A. Sudkamp, 3rd ed., Addison-Wesley, 2005 may be unavailable to purchase. The following book can be chosen as alternative: Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed.)
Module
Module 7
Participating study
Bachelor Applied Mathematics
Participating study
Required materials
Book
Languages and Machines: An Introduction to the Theory of Computer Science, Thomas A. Sudkamp, 3rd ed., Addison-Wesley, 2005
Book
When the book above is not available: Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed.), ISBN: 9781292039053
Recommended materials
-
Instructional modes
Lecture

Q&A

Tutorial

Tests
Languages & Machines

CloseHelpPrint
Kies de Nederlandse taal