1) Definire un automa deterministico che accetti le stringhe del tipo

1) Definire un automa deterministico che accetti le stringhe del tipo anbk con n e k positivi tali che
se n è pari allora k è dispari e viceversa. Determinare, col metodo dell’eliminazione degli stati
un’espressione regolare per il linguaggio accettato.
2) Definire un automa deterministico (rappresentato per mezzo di un grafo) che accetti le stringhe
sull’alfabeto {a, b} che non contengono tre ‘a’ consecutive e terminano con “ba”. Determinare
un’espressione regolare per il linguaggio accettato (con il metodo di eliminazione degli stati).
3) Definire un automa a stati finiti deterministico che accetti le stringhe sull'alfabeto {a, b} che
terminano con 'b' e in cui ogni 'b' è preceduta o seguita da almeno una 'a'. Determinare
un'espressione regolare per il linguaggio.
4) Dato l'automa M = (Q, S, F) con Q = {S, A, B, C, D} e F = {C} e definita dalla seguente
tabella:
a
b
S
{A}
{S, B}
A
{A}
{C}
B
{C}
{D}
C
{A}
{D}
D
{C}

{B}
costruire un automa deterministico equivalente.
5) Dato l'automa M = (Q, S, F) con Q = {S, A, B, C, D}, F = {C} e definita dalla seguente
tabella:

a
b
S
{S, A}
{A, B}
A
{C}
{A, D}
B
{A}
{B, D}
C
{A}
{B}
D
{D}
{C}
costruire un automa deterministico equivalente e minimizzarlo
6) Minimizzare l'automa M = (Q, S, F) con Q = {S, A, B, C, D, E, G, H}, F = {D, E, H} e
definita dalla seguente tabella:

a
b
S
A
C
A
A
B
B
D
S
C
E
A
D
G
B
E
G
C
G
H
E
H
D
G
7) Dimostrare che il linguaggio {an b a2n | n  0} è context-free ma non è regolare.
8) Dimostrare che il linguaggio {0n1k | n > 0, k > n+1} è context-free ma non è regolare.
9) Definire un automa a pila che accetti il linguaggio {an b a2n | n > 0}
10) Definire un automa a pila che accetti il linguaggio {0n1k | n > 0, k > n+1}