SluitenHelpPrint
Switch to English
Cursus: 202001361
202001361
Languages & Machines
Cursus informatie
Cursus202001361
Studiepunten (ECTS)3,5
CursustypeOnderwijseenheid
VoertaalEngels
Contactpersoondr. A. Skopalik
E-maila.skopalik@utwente.nl
Docenten
Docent
dr. M. Gerhold
Docent
dr.ing. E.M. Hahn
Examinator
dr. A. Skopalik
Contactpersoon van de cursus
dr. A. Skopalik
Docent
prof.dr. M.J. Uetz
Collegejaar2020
Aanvangsblok
2A
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
Cursusdoelen
After following this study unit, the student
  • is able 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).
Inhoud
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 a 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.
Bronnen van zelfstudie
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.)
Participating study
Bachelor Applied Mathematics
Participating study
Bachelor Technical Computer Science
Module
Module 7
Verplicht materiaal
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
Aanbevolen materiaal
-
Werkvormen
Hoorcollege

Vragenuur

Werkcollege

Toetsen
Languages & Machines

SluitenHelpPrint
Switch to English