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 zero oppure sono nella forma ababab…(ab)*.

Quindi:

• Nel caso in cui la parola fosse diversa da zero, 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 accettatore da cui leggere la A, per poi passare allo stato successivo solo in cui leggere la B. La macchina ritornerà allo stato iniziale dopo aver letto la B.

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

Andiamo ora a costruire la tabella di transizione:

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

• Cosa sono gli automi?
• Come si costruiscono gli automi?
• Automi e linguaggi regolari

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

Alla prossima!