Esercizio 1
(a)
Fornire la definizione formale di Automa a stati finiti deterministico e Automa
a stati finiti non deterministico.
(b)
Fornire l'automa a stati finiti deterministico che riconosca il linguaggio (a*bb)+c.
(c)
Dimostrare che il complemento di un linguaggio regolare e'
regolare.
Esercizio
2
(a)
Discutere delle differenze tra programmazione imperativa (imperative programming) e funzionale (functional
programming).
(b)
Definire informalmente la relazione di α-equivalenza tra lambda-termini.
Fornire la stessa definizione in modo formale.
(c)
Enunciare il teorema di Church-Rosser e dimostrare la
proprieta' di unicita'
delle forme normali per il lambda-calcolo. Dedurre poi da quest'ultima la proprieta' di consistenza per la teoria della
β-equivalenza.
Esercizio
3
Descrivere l'algoritmo che, dato un numero naturale n, fornisca la sua
rappresentazione posizionale in base B. Dimostrarne la correttezza.