次のような DFA を設計するにはどうすればよいですか。
Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
10 進数のセット。
L = {w| The decimal number represented by w leaves an odd remainder when divided by seven.}
これまでのところ、7 つの状態 (q0 - q6) を (手で) 引き出しており、奇数の q 状態が受け入れられています。
ここからどこへ行けばいいですか？
これを 2 つの手順で作成します。
状態が w を 7 で割った余りを追跡する DFA を構築します。これを行うには、状態 0、1、2、3、...、6 を構成し、それらを次のようにリンクします。w を 7 で割ったときに r の剰余が残り、次の桁が d である場合、次のようになります。 10r + d (mod 7) に相当する状態。これにより、各州から 10 個の発信リンクが提供されます。これらのリンクを計算するのは面倒ですが、一度だけ実行する必要があります。
マークは、1、3、および 5 を受け入れ、それ以外はすべて拒否と述べています。
お役に立てれば！