Introduce the students to the theory of languages and, at the same time, to the theory of automata. introduce computability and complexity paradigms. At the end of the course students should know new formal methodologies, should be able to critically review, from the perspective of their expressive potential, already known methodologies and should be able to classify problems from the point of view of the resources required for their solution.
teacher profile teaching materials
- Formal grammars: Chomsky grammars, productions, recognition of languages.
- Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure properties of regular languages, regular expressions and regular languages, Myhill-Nerode theorem.
- Context-free languages.
- Books (useful but non mandatory):
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente).
M. Sipser, Introduction to the Theory of Computation, Thompson.
Programme
- Elementary properties of languages: operations on languages, Kleene operator, regular expressions, cardinality of languages.- Formal grammars: Chomsky grammars, productions, recognition of languages.
- Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure properties of regular languages, regular expressions and regular languages, Myhill-Nerode theorem.
- Context-free languages.
Core Documentation
- Slides provided by the professor.- Books (useful but non mandatory):
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente).
M. Sipser, Introduction to the Theory of Computation, Thompson.
Type of delivery of the course
Traditional lectures and exercises.Type of evaluation
There is just one exam comprehending first and second modules. See second module. Attention please: during the COVID-19 lockdown periods the exam will be an oral test in accordance with Art.1 of Decreto Rettorale n°. 703 (5 May 2020). The oral test will be fundamental for passing the exam.