Um autômato não-determinístico pode ser simulado facilmente em uma string de entrada apenas mantendo-se a par dos estados em que o autômato está, e em que medida a string de entrada foi obtida. Mas como um transdutor não determinístico (um transdutor, é claro, pode traduzir símbolos de entrada para símbolos de saída e fornecer como saída uma cadeia, não apenas um valor booleano) pode ser simulado? Parece que isso é mais complicado, já que precisamos acompanhar, de alguma forma, as cadeias de saída, que podem ser numerosas por causa do não-determinismo.