Non determinismo

Note

Normalmente, una algoritmo è una sequenza deterministica di passi. Tuttavia in alcuni calcoli, come per il calcolo parallelo, il determinismo è il calcolo più comodo.

Si ricorda che non deterministico è diverso da probabilistico.

FSA non deterministici

Note

Si ha che la funzione di transizione diventa , e quindi ci restituirà un insieme. Estendendo alle stringhe: E quindi formalizziamo l'accettazione di una stringa come:

È sempre possibile ricavare un FSA-D da un FSA-ND . Esso sarà costituito da: Si ha che la determinizzazione di un FSA ha un costo, alla peggio:

Esempio FSA-ND riconoscitore di

center
In questo esempio si ha che: e

Esempio

center
In questo esempio abbiamo: Di conseguenza:

AP non deterministici

Note

Si ha che la funzione di transizione diventa , e quindi l'AP-ND accetta una stringa se esiste una sequenza con e .

Gli AP ND sono più potenti degli AP D, questo perché sono chiusi all'unione, però non sono chiusi rispetto all'intersezione.

Siccome la famiglia di linguaggi è chiusa rispetto a e non rispetto a , non può esserlo rispetto al complemento. Con gli AP ND la computazione termina sempre, ma se ho: Allora la è accettata nella computazione precedente, ma continua ad esserlo anche se scambio con .

MT non deterministiche

Note

Si ha che la funzione di transizione diventa . La configurazione, transizione, sequenza di transizioni e accettazione sono definite come negli altri casi. È possibile rappresentare una computazione con un grafico ad albero che rappresenta tutte le computazioni accettanti e non accettanti.

Si ha che è accettata da una MT ND solo se esiste un calcolo che termina in uno stato di accettazione. È possibile emulare una MT ND con una MT D, per farlo si percorre l'albero delle computazioni ND per stabilire se esiste un percorso che termina in uno stato di accettazione. Nel caso di un albero normale, esistono algoritmi consolidati per effettuare questa visita.

Nel caso di un albero in cui le computazioni non terminano si costruisce una MT D che scandisce le configurazioni della ND a partire dalle più vicine a .