state - 自己ループの 2 つの入力、確定的または非確定的ステート マシン?

Question

ウィキペディアは、決定論的ステート オートメーションは「入力文字列ごとにオートマトンの一意の計算 (または実行) を生成する」と述べています。

一意の文字列を計算するための可能なパスは1つしかないため、これを常に理解していました。その場合、以下は DSM です。

しかし今、私はこれを考え直し、説明を各入力文字列が単一の可能なパスを持ち、そのパスは他のすべての入力文字列から一意であると解釈しています。この場合、'11' と '12' は同じパスをたどるので、以下は DSM ではありません。

私の質問は、次は DSM または NDSM ですか?

Answer 1

それでも決定論的であり、各状態からの各入力に対して可能なパスは 1 つだけです。1 と 2 はそれ自体にのみ戻ることができます。非決定論的であるためには、入力には複数の可能なパスが必要です。入力 1 に、1 つの特定の状態から分岐する 2 つの可能な状態がある場合などです。

つまり、特定の入力に対して分岐パスがなく、グラフにε エッジがない場合、それは決定論的である必要があります。つまり、分岐パスがないため、どこに行くのかを確実に判断できます。上で描いたものから、特定の入力のパスをいつでも決定できます。