[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})

1.5.a.dot

1.5.b {w| wは部分文字列 baba を含まない}

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

1.5.b.dot

1.5.c {w| wは部分文字列 ab と ba のどちらも含まない}

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

1.5.c.dot

1.5.d {w| wは a*b* に属さない任意の文字列}

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

1.5.d.dot

1.5.e {w| wは (ab+)* に属さない任意の文字列}

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

1.5.e.dot

1.5.f {w| wは a*∪b* に属さない任意の文字列}

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

1.5.f.dot

1.5.g {w| wはちょうど二つの a は含まない任意の文字列}

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

1.5.g.dot

1.5.h {w| wは a でもなく b でもない任意の文字列}

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

1.5.h.dot