Descrizione informale degli Automi a Stati Finiti

Un Automa a Stati Finiti Deterministico e' un formalismo matematico che riconosce linguaggi.

Un Automa a stati finiti e` composto da:

un nastro d'ingresso (input tape), diviso in caselle, ciascuna delle quali contiene un simbolo appartenente alla stringa di ingresso;
un controllo finito (finite control), che in ogni istante si trova in uno degli stati assumibili dall'automa;
una testina di lettura (reading head) muovibile, che punta al simbolo del nastro di ingresso che deve essere letto nell'istante successivo;

Ad ogni intervallo di tempo, l'automa:

muove la testina di ingresso una casella a destra; essa si trovera` quindi sul simbolo da leggere nell'istante sucessivo;
cambia il proprio stato interno in funzione dello stato attuale e del simbolo letto;
stabilisce se lo stato attuale e` di riconoscimento;

Il processo di riconoscimento puo` concludersi con:

l'accettazione della stringa d'ingresso;
il rifiuto della stringa d'ingresso; oppure, non concludersi.
Una stringa e` accettata dall'automa quando:
non ci sono piu` simboli da leggere sul nastro di ingresso;
l'automa si trova in uno dei suoi stati finali.

Prossima Sessione

Ritorno all'Indice