Mobilité EUt+
Retour

Page du cours ✏️


Theoretical Computer Science
30.7332

Description
Learning objectives: 
Students acquire the skills to
  • develop an understanding of basic concepts, terms and relationships from the fields of automata theory and formal languages.
  • develop an understanding of basic proof methods. develop the ability to carry out simple proofs independently.
  • gain knowledge of the performance of different description tools and develop the ability to use the description tools independently.
  • gain knowledge of the relationship between the performance and algorithmic controllability of different description methods.
  • develop an understanding of non-deterministic machine models and their significance.
Course content:
  • Basic concepts: Words, alphabets, relations, operations over relations
  • Formal languages: The word problem, relation to general decision problems, efficient versus non-efficient solution algorithms for the word problem
  • Formal languages and automata theory: deterministic and non-deterministic finite automata, application of finite automata, equivalence of deterministic and non-deterministic finite automata, minimization algorithm, deterministic and non-deterministic basement automata
  • Formal languages and grammars: Chomsky hierarchy, efficiently enumerable languages and the word problem (undecidability of the word problem), context-sensitive grammars and the word problem (relation to the complexity class NP), right-linear grammars, closure properties, regular expressions (incl. (incl. use in scripting languages), termination properties, right-linear languages and the word problem (finite automata), context-sensitive grammars and the word problem, context-free grammars and the word problem (Chomsky normal form, CYK algorithm), applications of context-free languages (syntax of programming languages, XML-based languages and languages for describing communication protocols), context-free languages and non-deterministic basement automata, deterministic basement automata

Crédits ECTS
5

Langue d'enseignement
Deutsch

Langue d'examen
Deutsch

Langue des supports pédagogiques
Deutsch/English

Acquis d'apprentissage fondamentaux

Entité de gestion (faculté)
Computer Science Department (HDA)