Esercizio automa a stati finiti #9

157 Views 0 Comment

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:

automa1

Automa

 

transizione

Funzione di transizione

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

automa

Automa

transizione

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!


Continua a seguirci su:

Facebook Instagram Telegram Rss