私はこのようなものに本当に慣れていないので、ここでの無邪気さをお詫びします。
Deterministic Finite Automaton次の言語を認識するDFAを 作成します。
L= { w : w has at least two a's and an odd number of b's}.
これの各部分の自動化は(at least 2 a's, odd # of b's)個別に簡単に作成できます...誰かがそれらを1つに組み合わせる体系的な方法を説明できますか？ありがとう。
少なくとも 2 つあり、奇数である言語は通常の言語Lです。そのDFAは次のとおりです。ab
この DFA では、DFS概念的に 2 つの を組み合わせまし た。
DFA-1 = for odd number of `b`'s (placed vertically three times in diagram)
DFA-2 = for >= two a (placed Horizontally two times in diagram)
DFA はあまりにも象徴的で単純なので、両方の DFA を組み合わせる方法について説明する必要はないと思います。
bこの DFA を描画するには、偶数または奇数の s の数を常に追跡します。States 0, 2 and 4偶数回b来たことを意味します。したがって、この DFA を垂直方向に 2 つの部分に分割できます。下位bの状態は偶数で、上位の状態は奇数です。
また、奇数の場合は文字列が受け入れられるbため、最終状態は上部の状態のいずれかになります。
b状態は数だけではありませんaが最低でも良いと思い2ます。したがって、この DFA を水平方向に 3 つの部分に分割できます。ここで、s の数はaat で 0 state-0 and 1、as は at で 1 state-2 and 3、 s は ataで 2state-4 and 5です。最初の 2 つaの s の後は、文字列内で任意の数のs を使用できるため、stateとaで自己ループが発生します。q4q5
必要な状態の数は 6 です。奇数偶数の場合は 2 状態でbあり、少なくとも23 つの状態 a=0、a=1、a=2 であるため、2*3 = 6 です。
2台のオートマトンの製品を使用して行われます。