finite-automata - 右から5番目の記号として「1」を持つDFAの状態の最小数

Question

右から5番目の記号として「1」を持つ文字列を受け入れるためにDFAで必要な状態の最小数はいくつですか。文字列はアルファベット{0,1}の上に定義されます。

Answer 1

Myhill-Nerodeの定理は、この種の問題を解決するための便利なツールです。

アイデアは、「拡張を区別する」というアイデアを使用して、文字列の等価クラスのセットを構築することです。2 つの文字列 x と y を考えてみましょう。xz と yz のいずれかが言語に含まれる文字列 z が存在する場合、z は識別拡張であり、x と y は異なる等価クラスに属している必要があります。各等価クラスは、最小限の DFA で異なる状態にマップされます。

あなたが説明した言語について、x と y を {0,1} 上の異なる 5 文字の文字列の任意のペアとします。位置 n (右から数えて 1 から開始) が異なる場合、長さ 5-n の任意の文字列 z が識別拡張になります。x の位置 n に 0 があり、y の位置 n に 1 がある場合、 xz は拒否され、yz は受け入れられます。これにより、2 ⁵ = 32 の等価クラスが得られます。

^{s が長さ k < 5 文字の文字列である場合、それは 0 (5-k)} sと同じ等価クラスに属します(つまり、長さが 5 文字になるまで左に 0 パディングを追加します)。

s が長さ k > 5 文字の文字列の場合、その等価クラスは最後の 5 文字によって決定されます。

したがって、{0,1} を超えるすべての文字列は、上記の 32 の等価クラスのいずれかに分類され、Myhill-Nerode の定理により、この言語の最小 DFA には 32 の状態があります。