Два входа на автопилот, детерминированный или недетерминированный конечный автомат?

Question

Wikipedia утверждает, что автоматизация детерминированного состояния «производит уникальное вычисление (или запуск) автомата для каждой входной строки».

Я всегда понимал это, поскольку существует только один возможный путь для вычисления любой уникальной строки. В этом случае следующим является DSM.

Но теперь я переусердствую это и интерпретирую описание как каждую строку ввода, имеющую единственный возможный путь, и этот путь уникален из всех других входных строк. В этом случае следующее не является DSM, так как «11» и «12» следуют тем же путям.

Итак, мой вопрос заключается в следующем: DSM или NDSM?

Answer 1

Его еще детерминированным, есть только один возможный путь для каждого входа из каждого состояния. 1 и 2 может вернуться только к себе, поскольку он не является детерминированным, вход должен иметь несколько возможных путей. Например, если вход 1 имел два возможных состояния, ветвящихся из одного конкретного состояния.

Короче говоря, если на графике нет ветвящихся путей для определенного ввода, а на графике нет ε-edges, он должен быть детерминированным. то есть нет путей ветвления, мы можем точно определить, куда оно идет. Тот, который вы нарисовали выше, мы всегда можем определить путь для конкретного ввода.

Answer 2

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

Если мы вводим 1 в этот автомат, существует только один перемещение, определенное для 1 от начального до конечного состояния. После достижения конечного состояния нам все равно, будет ли вход 1 или 2. Если бы было задано несколько ходов для любого состояния, это были бы недетерминированные конечные автоматы.