決定性有限オートマトン

以下の問題を解いています。答えはわかったのですが、どのような手順で解けば正解に辿り着けるか（いわゆる解法）がわかりません。教えていただけると嬉しいです。

アルファベット Σ = {a, b} を使ってできるすべての文字列 w に対して、以下の条件を満たす文字列だけを受理するような、状態数が最小の DFA（決定性有限オートマトン）を作れ。
条件：3×(aの出現回数)+(bの出現回数) が4の倍数でない

No.4 回答者： usa3usa 回答日時： 2025/05/16 20:26

>作ったDFAが最小かどうかには

b、ｂｂ、ｂｂｂ、ｂｂｂｂ＝空、の4状態は最小必要である
４状態の解があれば、４状態が最小である
（Ｎｏ２さんの、q1,q2,q3,q0に対応）

で良いのでは？
状態遷移関数は　これらを輪にして、
aは左移動　（q0→q3→q2→q1→q0)、
ｂは右移動　（q0→q1→q2→q3→q0)、
出力関数は　q0は出力０（不受理）、その他は出力１（受理）

とすれば解である

No.3 回答者： ありものがたり 回答日時： 2025/05/16 13:47

ああ、「状態数が最小の」か。

作ったDFAが最小かどうかには
証明が必要だねえ。

No.2 回答者： mtrajcp 回答日時： 2025/05/16 12:32

A=(aの出現回数)

B=(bの出現回数)
とすると

3A+B=0(mod4),3A+B を 4 で割った余りが　0　の状態q0
3A+B=1(mod4),3A+B を 4 で割った余りが　1　の状態q1
3A+B=2(mod4),3A+B を 4 で割った余りが　2　の状態q2
3A+B=3(mod4),3A+B を 4 で割った余りが　3　の状態q3
の
4つの状態がある

Q={q0,q1,q2,q3}
Σ={a,b}
F={q1,q2,q3}

3A+B=4n→3(A+1)+B=4n+3だから
δ(q0,a)=q3
3A+B=4n→3A+B+1=4n+1だから
δ(q0,b)=q1
3A+B=4n+1→3(A+1)+B=4(n+1)だから
δ(q1,a)=q0
3A+B=4n+1→3A+B+1=4n+2だから
δ(q1,b)=q2
3A+B=4n+2→3(A+1)+B=4(n+1)+1だから
δ(q2,a)=q1
3A+B=4n+2→3A+B+1=4n+3だから
δ(q2,b)=q3
3A+B=4n+3→3(A+1)+B=4(n+1)+2だから
δ(q3,a)=q2
3A+B=4n+3→3A+B+1=4(n+1)だから
δ(q3,b)=q0

No.1 回答者： ありものがたり 回答日時： 2025/05/16 09:10

(aの出現回数を4で割った余り, bの出現回数を４で割った余り) の対を

状態として持つ状態遷移図を書けば、求められるでしょ。