Esercizio automa a stati finiti #10

88 Views 0 Comment

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:

automa

funzione

Ricaviamo ora l’ automa e la funzione di transizione relativi al secondo linguaggio:

automa2

funzione

Per semplicità evitiamo di trovare l’ automa intersezione.

Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.

Alla prossima!


Continua a seguirci su:

Facebook Instagram Telegram Rss