finite-automata - 必要な状態の最小数?

Question

アルファベット { a } を持つ言語Lの定義は、次のように与えられます。

L = {a ^nk | k > 0; n は正の整数定数です }

Lを認識するために DFA で必要な状態の数は?

---

私の意見では、k + 1 にする必要がありますが、よくわかりません。

Answer 1

言語 L は、n+1 個の状態を持つ DFA によって認識できます。

L の任意の文字列の長さが 0 mod n に一致することに注意してください。

状態のラベル n は整数 0、1、2、... n-1 で、それぞれの可能な剰余を表します。追加の状態 S は開始状態です。S は状態 1 への遷移を 1 回だけ行います。マシンが現在状態 i にある場合、入力時に状態 (i+1) mod n に移動します。状態 0 が唯一の受け入れ状態です。(空の文字列が L の一部である場合、S を削除して状態 0 を開始状態にすることができます)。

n+1 よりも少ない状態の DFA があり、まだ L を認識しているとします。文字列a ⁿ_{の処理中に発生した一連の状態 S 0}、S ₁、... S _nを考えてみましょう。a ⁿは L にあるため、 S _nは受け入れ状態である必要があります。しかし、この DFA には n+1 より少ない異なる状態があるため、ピジョンホールの原理により、少なくとも 2 回訪れた状態があったに違いありません。_{そのループを削除すると、S 0}から S _nまでの長さ < n の別のパス (および別の受け入れられた文字列) が得られます。しかし、L には n より短い文字列は含まれず、仮定に反します。したがって、状態が n+1 未満の DFA は L を認識しません。