複数の文字列の組み合わせ・文字列の逆転つぎは複数文字を組み合わせたり、文字列の反転などが含まれた言語が正則かどうかを判定してもらいます。今回の練習で一番むずかしいのがこのパターン3にあたります。正則か正則でないかを判定し、正則であれば最小状態決定性オートマトンを書き、正則でない場合は正則でないことの証明をしなさい。側の文字を1文字とすることで条件を簡単にすることができます。今回の場合は、連続する2文字が含まれていれば受理する、と言い換えられます。これは下のような有限オートマトンで記述できます。するだけではうまく背理法に持ち込めません。有限指数(異なる状態数の2項関係がある)としましょう。