Недетерминированный автомат можно легко смоделировать на входной строке, просто отслеживая состояния, в которых находится автомат, и то, как далеко он вошел во входную строку. Но как можно смоделировать недетерминированный преобразователь (конечно, преобразователь может преобразовывать входные символы в выходные символы и выдавать в качестве выходной строки, а не просто логическое значение)? Кажется, что это сложнее, так как нам нужно как-то отслеживать выходные строки, которые могут быть многочисленными из-за недетерминизма.