Corso di Laurea in Informatica
Corso di Linguaggi e Ambienti di Programmazione Esercitazione – 18 ottobre 2006
1. Scrivere le produzioni di una grammatica lineare destra e di una grammatica lineare sinistra che generino il linguaggio denotato dalla seguente espressione regolare: (ba+b)*a.
2. Fornire le produzioni di una grammatica che generi il linguaggio:
{bm a2k bm an / n > 0 ∧ m, k ≥ 0}
3. Sono vere le seguenti uguaglianze?:
a (b | Φ) a b = a (b | εε ) a b (r | s)* = (r | s | rs)*
4. Determinare la cardinalità dei seguenti linguaggi:
a b (c | a) | a (b | bc) Φ*| ε
Φ*| a a*b
5. Dimostrare che l’insieme {1m 22m / m ≥ 0} non è regolare 6. Dato il seguente automa:
A B
F H
C D
G E
1 1
0
1 0 1
1
1 1
0 0 1
0 0
0
a) costruire l’automa minimo equivalente;
b) trovare la grammatica lineare a partire dall’automa minimo;
c) fornire l’espressione regolare ricavata dalla grammatica.
7. Fornire un automa deterministico che riconosca le sequenze di zero di lunghezza multiplo di tre.
