Un autómata no determinista se puede simular fácilmente en una cadena de entrada con solo realizar un seguimiento de los estados en los que se encuentra el autómata y la distancia que ha alcanzado en la cadena de entrada. Pero, ¿cómo puede un transductor no determinista (un transductor, por supuesto, puede traducir símbolos de entrada a símbolos de salida, y dar como salida una cadena, no solo un valor booleano) simular? Parece que esto es más complicado, ya que necesitamos hacer un seguimiento, de alguna manera, de las cadenas de salida, que pueden ser numerosas debido al no determinismo.