Automa rifinito
Cos'è un automa rifinito
Un automa è rifinito se tutti gli stati sono raggiungibili e co-raggiungibili.
In un digrafo un nodo (stato) è raggiungibile se esiste un cammino orientato (parola) dallo stato iniziale.
Un nodo è co-raggiungibile se esiste un cammino orientato (parola) verso lo stato finale.
Un esempio pratico
In questo digrafo, escludendo il nodo iniziale (x0) e finale (x3), tutti i nodi sono sia raggiungibili che co-raggiungibili.
Sia x1 che x2 sono raggiungibili da x0 (stato iniziale).
Sia x1 che x2 co-raggiungibili perché hanno un cammino verso x3 (stato finale).
Come rifinire un automa
Qualsiasi automa può essere trasformato in un automa rifinito eliminando le transizioni verso gli stati non co-raggiungibili e quelle dagli stati non raggiungibili.
Esempio 1
Questo automa ha uno stato non co-raggiungibile (x2) ed è bloccante.
Eliminando la transizione non co-raggiungibile, l'automa diventa rifinito.
Nota. Quando l'automa è bloccante la rifinitura modifica anche il linguaggio generato dell'automa. In questo esempio il linguaggio passa da L={a,ban} a L={ban}. Nel caso degli automi non bloccanti, invece, il linguaggio generato dall'automa è lo stesso anche dopo l'operazione di rifinitura.
Esempio 2
Questo automa ha uno stato non raggiungibile (x2) ed è non bloccante.
Elimino la transizione non raggiungibile e lo trasformo in un automa rifinito.
Nota. In questo caso l'automa era non bloccante. Quindi il linguaggio generato non cambia dopo l'operazione di rifinitura. E' sempre L={ban}.
E così via
