Automa raggiungibile e co-raggiungibile
Automa raggiungibile
Un automa raggiungibile è un automa in cui tutti gli stati sono raggiungibili.
Rappresentando l'automa raggiungibile con un grafo orientato (digrafo), tutti i nodi sono raggiungibili.
Ogni nodo del digrafo è uno stato dell'automa a stati finiti.
Ogni arco è una transizione da uno stato a un altro.
A cosa serve la raggiungibilità? La raggiungibilità permette di capire in quali stati può trovarsi l'automa a partire da uno stato.
Automa non raggiungibile
Se uno o più stati non sono raggiungibili, l'automa è detto automa non raggiungibile.
Ad esempio, nel precedente digrafo lo stato x2 non è raggiungibile da x0 e x1.
Automa co-raggiungibile
Un automa co-raggiungibile ha tutti gli stati sono co-raggiungibili.
Nota. Un automa co-raggiungibile potrebbe essere raggiungibile o non raggiungibile. Ad esempio, gli stati x1 e x2 sono co-raggiungibili ma x2 non è raggiungibile. Quindi, l'automa è co-raggiungibile ma non raggiungibile.
Automa rifinito
Un automa rifinito ha tutti i nodi sia raggiungibili che co-raggiungibili.
Escludendo il nodo iniziale (x0) e finale (x3), tutti i nodi sono sia raggiungibili che co-raggiungibili.
Automa reversibile
Un automa è reversibile se ogni nodo è raggiungibile dallo stato iniziale e co-raggiungibile verso lo stato iniziale.
I nodi x1 e x2 sono sia raggiungibili da x0 e co-raggiungibili verso x0.
Dove x0 è lo stato iniziale.
A cosa serve la reversibilità? La reversibilità equivale a dire che il sistema può sempre essere reinizializzato.
E così via.
