|
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).
|
|
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.
|
 |
|
|
|
| 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.) |
| Bachelor Applied Mathematics |
| | Required materialsBook| 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 modesTestsLanguages & Machines
|
|
| |