ウィキペディアは、Deterministic State Automationが "入力文字列ごとにオートマトンの一意の計算（または実行）を生成する"と述べています。自己ループ上の2つの入力、確定的または非確定的な状態マシン？
私は、これは一意の文字列を計算するための可能なパスが1つしかないと常に理解しています。その場合、以下はDSMです。
しかし、私はこれを考えすぎて、記述を1つの可能なパスを持つ各入力文字列として解釈し、そのパスは他のすべての入力文字列から一意です。この場合、以下はDSMではなく、同じパスの後に '11'と '12'があるためです。
私の質問は次のDSMかNDSMですか？そのまだ決定的
、各状態からの各入力に対して1つだけの可能な経路が存在します。 1と2はそれ自身に戻ることができます。非決定論的であるため、入力には複数の可能なパスが必要です。入力1がある特定の状態から分岐する2つの可能な状態を有する場合など。
要するに、特定の入力に対して分岐パスがなく、グラフにε-edgesがない場合、それは決定論的でなければなりません。ブランチングパスがない場合は、どこに行くかを確かめることができます。上に描いたものは、特定の入力のパスを常に決めることができます。
状態のいずれかに対して定義されたすべての移動に対して一意のパスを持つのは確かに確定的有限オートマトンです。
このオートマトンに1を入力すると、ユニークの1つだけが初期状態から最終状態に定義されます。最終状態に到達した後、入力が1か2かどうかは気にしません。どの状態に対しても複数の移動が定義されていれば、非決定性有限オートマトンになります。