Lessico

Esercizio 9

Siano A e B due automi a stati finiti deterministici ed L(A), L(B) i linguaggi riconosciuti rispettivamente da A e da B. Indichiamo con A, rispettivamente B, l'automa costruito a partire da A, rispettivamente B:

1. Complementando l'insieme dei suoi stati finali.

2. Aggiungendo un ulteriore stato finale, che indichiamo con Y, avente transizioni: <<Y,a>,Y> per ogni carattere "a" dell'alfabeto

3. Aggiungendo, per ogni stato "s" dell'automa A e per ogni carattere "a" dell'alfabeto per il quale Move(s,a) e' indefinita, la transizione <<s,a>,Y>

Si dica:

1. Allorche A=<{s0, s1, s2}, {a,b,c}, s0, {s2}, {<<s0,a>,s1>, <<s1,b>,s2>, <<s1,c>,s2>, <<s2,a>,s2>, <<s2,b>,s2>}>:
• La definizione di A. 
• Quale linguaggio L(A) calcola il nuovo automa A.
2. Perche' gli automi cosi' ottenuti sono deterministici.
3. Perche' gli automi cosi' ottenuti calcolano il linguaggio complemento.
4. Sia U_d(A,B) un automa a stati finiti deterministico che riconosce il linguaggio unione di L(A) e di L(B). Si dica quale linguaggio calcola l'automa U_d(A,B), ottenuto applicando ad U_d(A,B) la trasformazione in tre passi descritta sopra.

[ Home | Back ]

Ultimo aggiornamento 7 Marzo 2202