"Fondamenti dell'Informatica II" ("Foundations of Computer Science II")
1. Nozioni centrali della teoria dei linguaggi formali. Gerarchia di Chomsky.
(1. Formal language basic notions. Chomsky hierarchy.)
2. Automi a stati finiti deterministici. Automi a stati finiti non deterministici.
epsilon-chiusura.
(2. Finite automata. Nondeterministic finite automata. Finite automata with epsilon-moves.)
3. Espressioni regolari. Teorema di Kleene. Pumping lemma per linguaggi regolari.
Proprieta' dei linguaggi regolari.
(3. Regular expressions. The Kleene theorem. Pumping lemma for regular sets. Properties of regular sets.)
4. Grammatiche context-free. Automi a pila. Linguaggi liberi dal contesto e proprieta'.
Forma normale di Chomsky. Pumping lemma per linguaggi liberi dal contesto. Algoritmo CYK.
(4. Context-free grammars. Pushdown automata. Properties of context-free languages.
Chomsky normal form. Pumping lemma for context-free languages. The CYK algorithm.)
5. Linguaggi formali multidimensionali e visuali. Modelli sintattici.
(5. Nonlinear and visual formal languages. Syntactical models.)
6. Grammatiche posizionali context-free.
(6. Context-free positional grammars.)
- Riferimenti bibliografici (Textbooks):
1-4:
Hopcroft, Motwani, Ullman, "Automi, Linguaggi e calcolabilita' ", Addison-Wesley
Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages and Computation, Addison-Wesley
volumi disponibili in biblioteca
(available at the Library)
5-6:
Materiale fornito dal docente (papers provided by the lecturer)
- Link utili (useful links):
Introduction to Automata Theory, Languages, and Computation
Slides for Introduction to Automata Theory, Languages, and Computation