Informazioni sull’esame
 Esame orale su tutti gli argomenti trattati a
lezione
 Seminario: studio di un argomento
avanzato, tipicamente di un formalismo che
estende uno di quelli visti a lezione
1
Modalita’ d’Esame
A scelta dello studente esame orale su tutti gli argomenti del corso
o seminario che approfondisca uno degli argomenti trattati a lezione
•In entrambi i casi gli esami dovranno svolgersi nei periodi di appello
d’esame standard con le seguenti modalita’:
(1) orale su appuntamento
(2) seminario su appuntamento (preferibilmente in date fissate), che
verranno comunicate sulla pagina web
Per iscriversi e’ obbligatorio inviare sempre la richiesta per e-mail con
almeno una decina di giorni di anticipo
2
Come si sceglie l’argomento del
seminario?
 Il seminario deve approndire uno degli argomenti
trattato a lezione
 Abbiamo studiato classi di linguaggi formali, e i rapporti
tra varie classi (gerarchie di linguaggi) e la loro specifica
 Per ogni classe: automi, grammatiche, le relazioni tra i
due formalismi
 Proprieta’ dei linguaggi formali e relativi algoritmi
3
Di cosa si tratta?
 Considerare una delle varie estensioni di automi e
grammatiche, studiate in letteratura e/o le loro
proprieta’, algoritmi
 Il materiale su cui studiare lo fornisce il docente (se
necessario), si tratta di argomenti di ricerca tipicamente
pubblicati su riviste scientifiche note
 Preparare una presentazione sull’argomento da
presentare in 30 minuti
 La comprensione degli aspetti tecnici cosi’ come delle
proprieta’ importanti dell’argomento assegnato fa parte
dell’esame
4
Possibili Argomenti
 P-system: questo formalismo rientra nell’ambito di
ricerca del natural computing, definire nuovi modelli di
specifica e calcolo che traggono ispirazione dai sistemi
biologici
 traggono ispirazione da lavori nell’ambito dei linguaggi
formali e delle grammatiche
 Formalmente, il linguaggio di specifica permette di
modellare una gerarchia di membrane, ognuna
contenente un multiinsieme di oggetti. Il sistema evolve
in base a regole di riscrittura
 Estensioni del linguaggio con probabilita’ e tempo (gia’
assegnato)
5
Possibili Argomenti
 Sistemi di Lindenmayer: questo formalismo e’ una
estensione delle grammatiche che introduce il
parallelismo nell’applicazione delle produzioni
 Esistono anche altri argomenti correlati, forme
particolari di grammatiche parallele
 Grammar Systems: e’ un insieme di grammatiche che
cooperano tra di loro per generare un linguaggio
6
Estensioni degli automi a stati
finiti







Automi temporizzati (prossime lezioni, una parte)
Automi temporizzati probabilistici (gia’ assegnato)
Automi sviluppati per modellare sistemi concorrenti o distruibuiti
Automi cooperanti, sistemi di automi paralleli che si sincronizzano
Automi Gerarchici
Automi per stringhe infinite, automi di Buchi e di Muller
Tree Automata
7
Argomenti relativi agli automi
temporizzati
 Vedremo solo alcuni aspetti a lezione
 Approndire gli algoritmi e le proprieta’ della classe di linguaggi
temporizzati definiti
 Automi temporizzati cooperanti
 Automi ibridi
 UPPAAL: un tool per la verifica di automi temporizzati, applicazione
interassante della teoria
 SPIN: tool per la verifica di sistemi concorrenti, distribuiti basato su
automi
8
Programma Svolto a Lezione







Automi a stati finiti. Espressioni regolari.
Proprietà degli insiemi regolari.
Grammatiche libere dal contesto. Automi a pila.
Proprietà dei linguaggi liberi dal contesto.
Linguaggi contestuali. Grammatiche non ristrette.
La gerarchia di Chomsky.
Automi Temporizzati
9