Como se pode simular transdutores finitos não determinísticos?

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 me...