Il capitolo 4 è tutto basato sulla dimostrazione che quanto visto nei capitoli precedenti è decidibile (o no).
ADFA è decidibile: si crea una macchina di Turing che, dati (B, w) con B automa e w stringa, simuli il DFA. Se la simulazione finisce in uno stato accettato, accetta, altrimenti rifiuta.
ANFA è decidibile: si potrebbe procedere come per la DFA e creare una TM che simuli il NFA, ma c'è un'altra strada: convertire il NFA in un DFA, e poi procedere come per il punto precedente.
AREX è decidibile: si converte l'espressione regolare in una NFA e si procede con il punto precedente.