Ein nicht deterministischer Automat kann auf einfache Weise in einer Eingabezeichenfolge simuliert werden, indem nur der Zustand des Automaten und der Grad der Eingabezeichenfolge verfolgt werden. Aber wie kann ein nicht deterministischer Wandler (ein Wandler kann natürlich Eingabesymbole in Ausgabesymbole umwandeln und als Ausgabe eine Zeichenfolge und nicht nur einen Booleschen Wert geben) simuliert werden? Es scheint, dass dies komplizierter ist, da wir irgendwie die Ausgabezeichenfolgen verfolgen müssen, die aufgrund des Nichtdeterminismus zahlreich sein können.