)\]それぞれの2進数のあまりが0,1,2のときに0を加えたとき、1を加えたときのあまりを表にし、最初に1が来た場合と0が来た場合を場合分けすると下のような状態遷移図で表せる。順番に書いていけば法則がわかるかもしれないので書いていこう。なることがわかるだろう。最後に文字列に制限がかかったバージョンも練習してみましょう。文字数制限をかけることによって言語が受理するかどうかが変化することがよくあります。5問ほど練習してみましょう。正則か正則でないかを判定しなさい。数を記憶させることで判定をしなければならない。数を記憶させなければならないため正則ではない。状態数を101個以上記憶させる必要はない(有限の記憶で判定ができる)。数を記憶させることで判定をする必要がある。数の記憶が必要なため、正則ではない。100文字以上来るかどうかを確かめればよい。数100個分の合計200個(有限個)の記憶状態があれば有限オートマトンを作成することができる。受理するかどうかを判定することができる。(101文字以上来た瞬間に非受理確定なので記憶させる必要がない)よって正則。(5)解答:正則である一見100文字以上(つまり無限大まで含まれる)の制限がついてるため正則ではないように見えるが実際は100文字未満か以上かを判定するだけでよいので100文字分あるかどうかを記憶させればよい。(100文字以上は必ず受理なので記憶させる必要なし)よって正則。さいごに今回はオートマトンと言語理論における正則判定の練習、正則だった場合の決定性オートマトン(最小状態の)、および正則でなかった場合の証明練習についてまとめました。基本的にオートマトンは理論さえ知ってしまえばあとはパズルゲーに近いので、ひたすら練習して頭を柔らかくしていきましょう!今回でしばらくオートマトンと言語理論の記事はお休みします。終わるような文字列*2:例えば101(10進数で5)に0を加え、1010とすると10進数では10(2倍)に、1011とすると10進数では11(2倍+1)となります。システムオートマトンPrologCLOSEサイト内検索を行います。はてなブログPro数学と情報が得意な大学生です。累計:リアルタイム現在の閲覧者数:。