w/計算理論の基礎[原著第2版]

Added parts are displayed like this.
Deleted parts are displayed ~~like this~~.

!1.4 '''<b, dのみ解答チェック済み>'''

""以下の各々の言語は，二つの簡単な言語の積集合である．それぞれについて，まず二つの簡単な言語の 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})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q3||q2
||!q3||q4||q3
||!q4||q4||q4

!!!少なくとも二つの bを受理する DFA
({r1,r2,r3}, {a,b}, δ, r1, {r3})
||!δ||!a||!b
||!r1||r1||r2
||!r2||r2||r3
||!r3||r3||r3

{{attach_view'1.4.a.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.a.dot)','1.4.a.dot','[A]1.4'}}

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

!!!ちょうど二つの aを含む文字列を受理する DFA
({q1,q2,q3,q4}, {a,b}, δ, q1, {q3})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q3||q2
||!q3||q4||q3
||!q4||q4||q4

!!!少なくとも二つの bを受理する DFA
({r1,r2,r3}, {a,b}, δ, r1, {r3})
||!δ||!a||!b
||!r1||r1||r2
||!r2||r2||r3
||!r3||r3||r3

{{attach_view'1.4.b.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.b.dot)','1.4.b.dot','[A]1.4'}}

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

!!!一つか二つの bを含む文字列を受理する DFA
({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q3})
||!δ||!a||!b
||!q1||q1||q2
||!q2||q2||q3
||!q3||q3||q4
||!q4||q4||q4

!!!偶数個の aを受理する DFA
({r1,r2}, {a,b}, δ, r1, {r1})
||!δ||!a||!b
||!r1||r2||r1
||!r2||r1||r2

{{attach_view'1.4.c.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.c.dot)','1.4.c.dot','[A]1.4'}}

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

!!!すべての aがひとつ以上の bのあとにくる文字列を受理する DFA
({q1,q2,q3}, {a,b}, δ, q1, {q1,q2})
||!δ||!a||!b
||!q1||q3||q2
||!q2||q1||q2
||!q3||q3||q3

!!!偶数個の aを受理する DFA
({r1,r2}, {a,b}, δ, r1, {r1})
||!δ||!a||!b
||!r1||r2||r1
||!r2||r1||r2

{{attach_view'1.4.d.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.d.dot)','1.4.d.dot','[A]1.4'}}

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

!!!aではじまる
({q1,q2,q3}, {a,b}, δ, q1, {q2})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q2
||!q3||q3||q3

!!!高々一つの b
({r1,r2,r3}, {a,b}, δ, r1, {r1,r2})
||!δ||!a||!b
||!r1||r1||r2
||!r2||r2||r3
||!r3||r3||r3

{{attach_view'1.4.e.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.e.dot)','1.4.e.dot','[A]1.4'}}

!!!aで始まり、0か 1つの bをもつ文字列を受理する DFA
({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q3})
||!δ||!a||!b
||!q1||q2||q4
||!q2||q2||q3
||!q3||q3||q4
||!q4||q4||q4

{{attach_view'1.4.e2.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.e2.dot, 間違えて一息に作ってしまいました)','1.4.e2.dot','[A]1.4'}}

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

!!!奇数個の aをもつ文字列を受理する DFA
({q1,q2}, {a,b}, δ, q1, {q2})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q1||q2

!!!bで終わる文字列を受理する DFA
({r1,r2}, {a,b}, δ, r1, {r2})
||!δ||!a||!b
||!r1||r1||r2
||!r2||r1||r2

{{attach_view'1.4.f.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.f.dot)','1.4.f.dot','[A]1.4'}}

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

!!!奇数個の aをもつ文字列を受理する DFA
({q1,q2}, {a,b}, δ, q1, {q2})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q1||q2

!!!長さが偶数の文字列を受理する DFA
({r1,r2}, {a,b}, δ, r1, {r1})
||!δ||!a||!b
||!r1||r2||r2
||!r2||r1||r1

{{attach_view'1.4.g.gif','[A]1.4'}}
{{attach_anchor_string'ソースファイル(1.4.g.dot)','1.4.g.dot','[A]1.4'}}

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

{{attach_view'1.4.d(answer-of-a-after-b).gif', '[A]1.4'}}

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

w/計算理論の基礎[原著第2版] - [A]1.4 Diff

w/計算理論の基礎[原著第2版]

更新履歴(20件)