Si vuole costruire l’ automa a stati finiti per riconoscere il seguente linguaggio:
L = {w non contiene ’11’, w = x1,x2…xn, x1=xn | n ∈ {0,1}}
Esaminand0 il linguaggio notiamo che:
- Le parole del linguaggio non possono contenere due ‘1’ consecutivi;
- Le parole del linguaggio devono iniziare e finire con lo stesso simbolo.
Per la proprietà di chiusura possiamo scrivere il linguaggio come:
L = L1 ∩ L2 con:
- L1: {w non contiene ’11};
- L2: {w = x1,x2…xn, x1=xn | n ∈ {0,1}}
Iniziamo ricavando l’ automa e la funzione di transizione del primo linguaggio:
Automa
Funzione di transizione
Ricaviamo ora l’ automa e la funzione di transizione relativi al secondo linguaggio:
Automa
Funzione di transizione
Per semplicità evitiamo di trovare l’ automa intersezione.
Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.
Alla prossima!
