[A]1.4

以下の各々の言語は，二つの簡単な言語の積集合である．それぞれについて，まず二つの簡単な言語の DFAを構成し，次に脚注4 (54ページ)で述べた構成法を用いて連結させ，与えられた言語を認識する DFAの状態遷移図を作れ．すべてにおいて，Σ={a,b}とする．

• a. {w| wは少なくとも三つの aと，少なくとも二つの bをもつ}
• b. {w| wはちょうど二つの aと，少なくとも二つの bをもつ}
• c. {w| wは偶数個の aと，一つあるいは二つの bをもつ}
• d. {w| wは偶数個の aをもち，かつ，各々の aは少なくとも一つの bの後にくる}
• e. {w| wは aで始まり，かつ，高々一つの bをもつ}
• f. {w| wは奇数個の aをもち，かつ，bで終わる}
• g. {w| wは長さが偶数であり，かつ，奇数個の aをもつ}

a. {w| wは少なくとも三つの aと，少なくとも二つの bをもつ}

少なくとも三つの aを受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})

少なくとも二つの bを受理する DFA

({r1,r2,r3}, {a,b}, δ, r1, {r3})

ソースファイル(1.4.a.dot)

b. {w| wはちょうど二つの aと，少なくとも二つの bをもつ}

ちょうど二つの aを含む文字列を受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q3})

少なくとも二つの bを受理する DFA

({r1,r2,r3}, {a,b}, δ, r1, {r3})

ソースファイル(1.4.b.dot)

c. {w| wは偶数個の aと，一つあるいは二つの bをもつ}

一つか二つの bを含む文字列を受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q3})

偶数個の aを受理する DFA

({r1,r2}, {a,b}, δ, r1, {r1})

ソースファイル(1.4.c.dot)

d. {w| wは偶数個の aをもち，かつ，各々の aは少なくとも一つの bの後にくる}

すべての aがひとつ以上の bのあとにくる文字列を受理する DFA

({q1,q2,q3}, {a,b}, δ, q1, {q1,q2})

偶数個の aを受理する DFA

({r1,r2}, {a,b}, δ, r1, {r1})

ソースファイル(1.4.d.dot)

e. {w| wは aで始まり，かつ，高々一つの bをもつ}

aではじまる

({q1,q2,q3}, {a,b}, δ, q1, {q2})

高々一つの b

({r1,r2,r3}, {a,b}, δ, r1, {r1,r2})

ソースファイル(1.4.e.dot)

aで始まり、0か 1つの bをもつ文字列を受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q3})

ソースファイル(1.4.e2.dot, 間違えて一息に作ってしまいました)

f. {w| wは奇数個の aをもち，かつ，bで終わる}

奇数個の aをもつ文字列を受理する DFA

({q1,q2}, {a,b}, δ, q1, {q2})

bで終わる文字列を受理する DFA

({r1,r2}, {a,b}, δ, r1, {r2})

ソースファイル(1.4.f.dot)

g. {w| wは長さが偶数であり，かつ，奇数個の aをもつ}

奇数個の aをもつ文字列を受理する DFA

({q1,q2}, {a,b}, δ, q1, {q2})

長さが偶数の文字列を受理する DFA

({r1,r2}, {a,b}, δ, r1, {r1})

ソースファイル(1.4.g.dot)

1.4.d の解答について

答案と解答が食い違っていたのだが、原因は「各々の a は，少なくとも一つの b の後にくる」言語の DFAがそれぞれで違っていたから。解答にはこういう図が載っているが……

• a で始まる文字列を受理する可能性があるのでは？
• a で終わる文字列がすべて受理されないのでは？