Automat niedeterministyczny można łatwo symulować na łańcuchu wejściowym, śledząc tylko stany, w których znajduje się automat, oraz odległość, jaką osiągnął w ciągu wejściowym. Ale jak można symulować przetwornik niedeterministyczny (przetwornik, oczywiście, może tłumaczyć symbole wejściowe na symbole wyjściowe i przekazywać jako wyjście ciąg, a nie tylko wartość logiczną)? Wydaje się, że jest to bardziej skomplikowane, ponieważ musimy jakoś śledzić ciągi wyjściowe, które mogą być liczne z powodu niedeterminizmu.