決定性オートマトン （数学）

Question

等価な最簡形の決定性オートマトンの状態の数とはなんのことですか？

受理状態のことを指しているのですか？

Answer 1

等価な最簡形の決定性オートマトンの状態の数とはなんのことですか？

書いてのとおりです。提示されたオートマトンと同じ記号列を受理する（=等価）決定性オートマトンとして、いちばん状態数が少ないもの（=最簡形）の状態数です。

受理状態のことを指しているのですか？

直接は関係ありません。

Answer 2

その丸で囲んでるのが状態です。この図では 8 つあります。

低評価されていますが、間違っているところをコメントしてください。8 つあるのはあくまでも「この図では」ということで、書き直したものの話は今はしていません。状態自体について説明しています。

Comments

[Zuishin]

もっとも、遷移できない状態がいくつかあるし、すでに遷移先が一意に決まっているので、この問題自体なんだこりゃですが。

[maisumakun]

「等価な最簡形の決定性オートマトンの状態の数」全体が疑問だと考えたので、これではその疑問は解消しないと判断しました。

[Zuishin]

「状態の数」が何を数えればいいのかわからないという質問と認識していました。

「等価な最簡形の決定性オートマトン」からわからないという質問なら了解です。