Esercizio automa a stati finiti #4

89 Views 0 Comment

Si vuole costruire l’ automa a stati finiti per riconoscere il seguente linguaggio: L = {(AB)+}.

Esaminando il linguaggio notiamo preliminarmente che le parole hanno lunghezza maggiore di zero e sono nella forma ababab…(ab)+.

Quindi:

  • Bisogna dapprima leggere una A;
  • Dopo aver letto la A bisogna necessariamente leggere una B.

Potremmo dire che la macchina partirà da uno stato iniziale da cui leggere la A, per poi passare allo stato successivo in cui leggere la B. Dopo aver letto la prima B, la macchina può leggere una A ed una B alternate, oppure terminare la computazione.

N.B. La macchina può terminare la computazione SOLO dopo aver letto ALMENO UNA VOLTA una A ed una B alternate.

L’ automa dunque avrà una forma simile a questa:

automa

Andiamo ora a costruire la tabella di transizione:

tabella

Se non sai cosa sono gli automi o vuoi avere una rinfrescata su questo argomento ti consiglio di leggerti questi articoli:

 

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

Alla prossima!


Continua a seguirci su:

Facebook Instagram Telegram Rss