w/計算理論の基礎[原著第2版] - [A]1.5 Diff
- Added parts are displayed like this.
- Deleted parts are displayed
like this.
!1.5
""DFAを構成し，状態遷移図を作れ，すべてにおいて，Σ={a,b}とする．(問題文 大幅に省略)
""
""*a. {w| wは部分文字列 ab を含まない}
""*b. {w| wは部分文字列 baba を含まない}
""*c. {w| wは部分文字列 ab と ba のどちらも含まない}
""*d. {w| wは a*b* に属さない任意の文字列}
""*e. {w| wは (ab+)* に属さない任意の文字列}
""*f. {w| wは a*∪b* に属さない任意の文字列}
""*g. {w| wはちょうど二つの a は含まない任意の文字列}
""*h. {w| wは a でもなく b でもない任意の文字列}
!!1.5.a {w| wは部分文字列 ab を含まない}
({q1,q2,q3}, {a,b}, δ, q1, {q1,q2})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q2||q3
||!q3||q3||q3
{{attach_view'1.5.a.gif','[A]1.5'}}{{attach_anchor'1.5.a.dot','[A]1.5'}}
!!1.5.b {w| wは部分文字列 baba を含まない}
({q1,q2,q3,q4,q5}, {a,b}, δ, q1, {q1,q2,q3,q4})
||!δ||!a||!b
||!q1||q1||q2
||!q2||q3||q2
||!q3||q1||q4
||!q4||q5||q2
||!q5||q5||q5
{{attach_view'1.5.b.gif','[A]1.5'}}{{attach_anchor'1.5.b.dot','[A]1.5'}}
!!1.5.c {w| wは部分文字列 ab と ba のどちらも含まない}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q2,q3})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q4
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.c.gif','[A]1.5'}}{{attach_anchor'1.5.c.dot','[A]1.5'}}
!!1.5.d {w| wは a*b* に属さない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q3
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.d.gif','[A]1.5'}}{{attach_anchor'1.5.d.dot','[A]1.5'}}
!!1.5.e {w| wは (ab+)* に属さない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q4})
||!δ||!a||!b
||!q1||q2||q4
||!q2||q4||q3
||!q3||q2||q3
||!q4||q4||q4
{{attach_view'1.5.e.gif','[A]1.5'}}{{attach_anchor'1.5.e.dot','[A]1.5'}}
!!1.5.f {w| wは a*∪b* に属さない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q4
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.f.gif','[A]1.5'}}{{attach_anchor'1.5.f.dot','[A]1.5'}}
!!1.5.g {w| wはちょうど二つの a は含まない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q2,q4})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q3||q2
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.g.gif','[A]1.5'}}{{attach_anchor'1.5.g.dot','[A]1.5'}}
!!1.5.h {w| wは a でもなく b でもない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q4})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q4||q4
||!q3||q4||q4
||!q4||q4||q4
{{attach_view'1.5.h.gif','[A]1.5'}}{{attach_anchor'1.5.h.dot','[A]1.5'}}
""DFAを構成し，状態遷移図を作れ，すべてにおいて，Σ={a,b}とする．(問題文 大幅に省略)
""
""*a. {w| wは部分文字列 ab を含まない}
""*b. {w| wは部分文字列 baba を含まない}
""*c. {w| wは部分文字列 ab と ba のどちらも含まない}
""*d. {w| wは a*b* に属さない任意の文字列}
""*e. {w| wは (ab+)* に属さない任意の文字列}
""*f. {w| wは a*∪b* に属さない任意の文字列}
""*g. {w| wはちょうど二つの a は含まない任意の文字列}
""*h. {w| wは a でもなく b でもない任意の文字列}
!!1.5.a {w| wは部分文字列 ab を含まない}
({q1,q2,q3}, {a,b}, δ, q1, {q1,q2})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q2||q3
||!q3||q3||q3
{{attach_view'1.5.a.gif','[A]1.5'}}{{attach_anchor'1.5.a.dot','[A]1.5'}}
!!1.5.b {w| wは部分文字列 baba を含まない}
({q1,q2,q3,q4,q5}, {a,b}, δ, q1, {q1,q2,q3,q4})
||!δ||!a||!b
||!q1||q1||q2
||!q2||q3||q2
||!q3||q1||q4
||!q4||q5||q2
||!q5||q5||q5
{{attach_view'1.5.b.gif','[A]1.5'}}{{attach_anchor'1.5.b.dot','[A]1.5'}}
!!1.5.c {w| wは部分文字列 ab と ba のどちらも含まない}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q2,q3})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q4
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.c.gif','[A]1.5'}}{{attach_anchor'1.5.c.dot','[A]1.5'}}
!!1.5.d {w| wは a*b* に属さない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q3
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.d.gif','[A]1.5'}}{{attach_anchor'1.5.d.dot','[A]1.5'}}
!!1.5.e {w| wは (ab+)* に属さない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q4})
||!δ||!a||!b
||!q1||q2||q4
||!q2||q4||q3
||!q3||q2||q3
||!q4||q4||q4
{{attach_view'1.5.e.gif','[A]1.5'}}{{attach_anchor'1.5.e.dot','[A]1.5'}}
!!1.5.f {w| wは a*∪b* に属さない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q2||q4
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.f.gif','[A]1.5'}}{{attach_anchor'1.5.f.dot','[A]1.5'}}
!!1.5.g {w| wはちょうど二つの a は含まない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q2,q4})
||!δ||!a||!b
||!q1||q2||q1
||!q2||q3||q2
||!q3||q4||q3
||!q4||q4||q4
{{attach_view'1.5.g.gif','[A]1.5'}}{{attach_anchor'1.5.g.dot','[A]1.5'}}
!!1.5.h {w| wは a でもなく b でもない任意の文字列}
({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q4})
||!δ||!a||!b
||!q1||q2||q3
||!q2||q4||q4
||!q3||q4||q4
||!q4||q4||q4
{{attach_view'1.5.h.gif','[A]1.5'}}{{attach_anchor'1.5.h.dot','[A]1.5'}}