Unterabschnitte
Eine NTM
![$\tau$](img64.png)
entscheidet eine Sprache
![$L$](img124.png)
falls gilt:
1.
![$L(\tau)=L$](img127.png)
und
2. Der Berechnungsbaum für jedes mögliche Eingabewort
![$w\in\{0,1\}^{*}$](img194.png)
ist endlich, d.h. jedes Wort wird nach endlicher Zeit entweder akzeptiert oder verworfen.
Aus jeder NTM kann man eine DTM machen. Man geht dabei den Berechnungsbaum mit einer Breitensuche durch
19.
Fußnoten
- ... durch19
- Hier darf man keine Tiefensuche verwenden. Das kann unter Umständen ins Auge gehen, da ein Berechnungsbaum ins Unendliche ragt, während ein anderer schon lange akzeptiert hat, man aber im unendlichen Berechnungsbaum immer tiefer geht und nie zum Ende kommt.