Classroom lessons.
Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Introduction to formal languages:
Grammars and recognizers.
Finite state automata and regular languages:
Finite state automata: deterministic, nondeterministic, with epsilon-transitions.
The class of AF-regular languages.
Regular expressions and regular languages.
Kleene's theorem.
Pumping lemma for regular languages.
Pumping Lemma and decidability algorithms for regular languages.
Myhill-Nerode's theorem.
Context-free grammars:
Parse trees.
Simplification of context-free grammars: useless symbols; epsilon-productions; unit-productions.
Chomsky Normal Form.
Greibach Normal Form.
Ambiguous, non-ambiguous and inherently ambiguous grammars.
Pumping Lemma for context-free languages.
Ogden's Lemma.
Membership problem for context-free languages.
Pushdown Automata:
Acceptance by final state and by empty stack.
Deterministic pushdown automata.
Pushdown automata and context-free grammars.
Turing Machines:
Recursively enumerable languages.
Deterministic e non-deterministic Turing Machines.
Turing Machines and unrestricted grammars.
Linear-bounded automata and context-sensitive languages:
Definition and examples.
Linear-bounded automata and context-sensitive grammars.
Chomsky Hierarchy
1) John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.
2) John E. Hopcroft, Jeffrey D Ullman. Introduction to automata theory, languages and computation, Addison-Wesley