Si vuole costruire l’ automa a stati finiti per riconoscere il seguente linguaggio:
L = {w ∈ {0,1}* | w contiene almeno due volte ’11’ e al più una volta ’00’ }
Esaminand0 il linguaggio notiamo che:
- Le parole del linguaggio devono contenere due ‘1’ consecutivi almeno due volte;
- Le parole del linguaggio devono contenere al massimo una volta ’00’.
Per la proprietà di chiusura possiamo scrivere il linguaggio come:
L = L1 ∩ L2 con:
- L1: {w contiene almeno due volte ’11’};
- L2: {w contiene al più una volta ’00’ }
Iniziamo ricavando l’ automa e la funzione di transizione del primo linguaggio:
Ricaviamo ora l’ automa e la funzione di transizione relativi al secondo linguaggio:
Per semplicità evitiamo di trovare l’ automa intersezione.
Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.
Alla prossima!
