Я бы начал в конце.Обратное направление (да, это означает, что гейт теперь может получить одно значение и вывести два) и использовать строку в качестве входных данных в обратном порядке.всякий раз, когда вы достигаете какого-либо элемента ворот или черного ящика, вы получаете его вывод;выяснить все возможные входы, которые могли бы привести к этому выходу, и продолжать идти назад недетерминированным образом.
Если в конце строки вы достигнете некоторого ввода (или группы входов), то этот (или эти) вход будетвход, который производит данную строку.В противном случае строка не может быть сгенерирована на этой машине.
Другой подход (иногда более простой, иногда нет) состоит в том, чтобы попытаться увидеть, какие все строки генерирует машина, или попробовать инайти некоторый атрибут, которому должны удовлетворять все эти строки, а заданная строка - нет (например, если вы не знаете точно, какие строки генерируются машиной, но вы знаете, что все они начинаются с «A», а данная строка не«т).