finite-automata - この言語は規則的ですか？

Question

n(n-1)(n-2)/6+n(n-1)/2+1 個の {0,1}^n をすべての n に対して受け入れる言語は正規言語ですか?

それらの言語の dfa を描画する質問がありますが、それが通常のものかどうかさえわかりません。

Answer 1

これは宿題のように聞こえますが、問題は次のとおりだと思います: n(n-1)(n-2)/6+n(n-1)/2+1 個の長さの単語を正確に受け入れる DFA を描くアルファベット {0,1})。オートマトンを 2 つの DFA の共通部分として構築します。

最初のオートマトンは長さ n の単語を受け入れます。これはとても簡単です - n+1 個の状態の連鎖があります。最初の状態は初期状態で、最後の状態のみが受け入れられます。すべての状態には、チェーン内の次の状態への 0,1 というラベルの付いた遷移があります。受け入れ状態には、発信遷移はありません。

2 番目のオートマトンは、1、2、または 3 個の 1 が含まれる単語を受け入れます。また、非常に簡単です。q_0、q_1、q_2、q_sink の 4 つの状態が必要です。状態 q_0 は初期状態であり、状態 q_0、q_1、q_2 が受け入れられており、0 の自己ループがあります。遷移 q_0 --1--> q_1 --1--> q_2 --1-- があります。 >q_sink。最後に、q_sink が拒否され、0,1 の自己ループがあります。

オートマトンの交差を構築するには、2 つのオートマトンの積が必要です。これは一般的な構造であり、それほど難しくありません。