Automata and languages
- Overview
- Assessment methods
- Learning objectives
- Contents
- Bibliography
- Delivery method
- Teaching methods
- Contacts/Info
The course does not have formal prerequisites but notions from the
courses of "Algorithm and Data structures", "Computer programming",
Algebra and Logic" and "Mathematical logic" will be useful.
The exam will consist of an oral examination testing student's
knowledge of the themes presented in the lectures.
Learn the fundamental concepts of automata, languages and computation
theory. Develop the ability to formalize and to model systems with
the adequate level of abstraction and to solve complex problems.
Deterministic finite automata (DFA), non-deterministic finite automata
(NFA) and finite automata with ε-moves (ε-NFA). Notions of
comuputations and accepted language. Equivalence between DFA and NFA
and between NFA and ε-NFA.
Regular expressions. Equivalence between regular expressions and
ε-NFA.
Regular languages: main properties and Pumping Lemma.
Context-free grammars. Derivation trees, ambiguous grammars.
Pushdown automata (PDA): equivalnece between acceptance by final stack
and acceptance by empty stack. Equivalence between PDA and
context-free grammars.
Context-free languages: mani properties and Pumping Lemma.
The Chomsky hierarchy.
Turing machines recursively enumerable languages and undecidable
problems.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Pearson Education, 3rd edition, 2008.
48 hours of lectures, 102 hours of study.
Office hours: by appointment via email.