Как найти уникальный вход и выход для конечного автомата

Question

Как бы идти о выяснить, имеет ли каждое государство имеет уникальную последовательность ввода/вывода? Существует ли стандартизированный метод или метод? Кажется, я ничего не могу найти в Интернете.

Спасибо за помощь!

Answer 1

Для детерминированных FSM (то есть, один без эпсилона переходов состояний), существует единственная входная последовательность, ведущая к состоянию, если и только если выполняются следующие условия:

1) Там должен существовать путь к штат. (Изолированное недостижимое состояние не может быть квалифицировано).

2) Нет пути, который возвращается в исходное состояние (в противном случае прямой переход к целевому состоянию достигнет его и марш, который возвращается в исходное состояние, а затем также работает прямой марш).

3) Для каждого состояния S либо целевое состояние недоступно от S, либо S является целевым состоянием, или существует уникальный путь от состояния начала до S, и существует уникальный путь от S к целевому состоянию.

Предполагая, что вы используете представление объекта Directed Graph, это будет означать, что на графе, который заканчивается в начальном состоянии, нет ребер, и что для каждого состояния S в графе тоже нет пути от S к цели, или есть уникальный.

Если вы пытаетесь найти это в коде, вы можете, вероятно, использовать модифицированный Dijkstra's algorithm для решения этой проблемы.

Обратите внимание, что это только адреса, имеющие уникальную последовательность ввода. Наличие уникальной последовательности вывода требует большей осторожности, потому что на самом деле может быть более одной входной последовательности, которая создает одну и ту же последовательность вывода. Однако идеи одинаковы, но вы должны изменить третий критерий:

3) Для каждого состояния S либо целевое состояние недоступно от S, либо S является целевым состоянием, или если S и T оба имеют путь к целевому состоянию, они должны генерировать одну и ту же выходную последовательность, а выходная последовательность, сгенерированная из начального состояния в S, и выходная последовательность, сгенерированная из начального состояния в T, должны быть одинаковыми.

Опять же, модифицированный Дийкстра, вероятно, лучший вариант.