
スポンサードリンク
こんにちは、ももやまです。
今回はとある言語が正則かどうかを判定する練習、および正則だった場合に決定性オートマトンを書く練習、および正則でない場合に証明を書く練習をする総復習問題を作成しました。
ぜひ練習にお使いください。
前回の記事(第07羽)はこちら!
(文脈自由文法は総復習の内容には入れてないので各自で復習してください。)
演習前の注意
(1) 特に指示のない場合、
(2) 特に指示のない場合、
(つまり
(3) Myhill-Nerodeで証明する際に最初の定義部分は省略して書いているのでご了承ください。
↓詳しいMyhill-Nerodeの定理の書き方などはこちらでご覧ください
目次 [hide]
スポンサードリンク
パターン1 a^mとb^nの連接パターン
では、まずは基本的な
練習1
つぎの(1), (2)の言語
(1)
(2)
(3)
解説1
正則かどうかを判定する際に大切なのが、無限に続く文字列に対し、有限個の状態でオートマトンを記述できるかどうかです。有限個の状態のオートマトン(有限オートマトン)を書くことができれば正則であるといえます。
逆に無限の文字列が来ることを考えたとき、無限の状態を記憶しないと受理するどうかを判定できない場合は正則とはいえません。
(1)
正則判定:正則である
(2)
正則判定:正則ではない
(
有限指数より
また、右不変より
よって正則ではない。
(3)
正則判定:正則である。
文字列
↓
スポンサードリンク
パターン2 文字数系
つぎに文字数を基準とした言語が正則となるかどうかの判定をしてもらいましょう。
※注意
練習2
つぎの(1), (2), (3)の言語
(1)
(2)
(3)
(4)
解説2
(1)
正則判定:正則ではない
((無限に続く)文字列の
有限指数より
また、右不変より
よって正則ではない。
(2)
正則判定:正則である
参考までに条件
→状態1,2,3が受理状態となる。
→状態1,4が受理状態となる。
と変化します。
(3)
正則判定:正則ではない
(ポイント
有限指数より
また、右不変より
よって正則ではない。
(4)
正則判定:正則ではない
(
[証明]
有限指数より
また、右不変より
(左辺を a:b = 1:2 にするように右不変を適用する。)
よって正則ではない。
スポンサードリンク
パターン3 複数の文字列の組み合わせ・文字列の逆転
つぎは複数文字を組み合わせたり、文字列の反転などが含まれた言語が正則かどうかを判定してもらいます。
今回の練習で一番むずかしいのがこのパターン3にあたります。
練習3
つぎの(1)〜(6)の言語
※
(1)
(2)
(3)
(4)
(5)
(6)
解答3
(1)
このようなパターンは、下のように
今回の場合は、連続する2文字が含まれていれば受理する、と言い換えられます。これは下のような有限オートマトンで記述できます。
(2)
正則判定:正則ではない
(うまく文字を押し込めない場合は正則とはなりません……)
ポイントは有限指数の決め方、ただ単に
有限指数より
また、右不変より
(左辺を a:b = 1:2 にするように右不変を適用する。)
よって正則ではない。
(3)
この問題も
文字列の始点と終点の文字が一致しているような文字列*1を受理するような言語が正則かどうか、と言い換えることができます。これは下のような有限オートマトンを書くことができます。
(4)
このようにすべての変数が
今回の場合、
もちろん、
下のような有限オートマトンが
(5)
(お詫び:証明部分を間違えていたため、11月7日に修正を行いました。申し訳有りません。修正箇所を赤色で示しています。)
正則判定:正則ではない
(実は(2)のパターン(
このように実際に何個か試してみましょう。
有限指数より
また、右不変より
よって正則ではない。
(6)
正則判定:正則ではない
(おそらく今回の演習の中で一番むずかしい問題。)
(5)のように実際に何個か試してみましょう。
有限指数より
また、右不変より
よって正則ではない。
パターン4 2進数に絡んだ問題
つぎに、0,1で与えられる文字列を2進数と考えるタイプの問題も練習していきましょう。
ここからは
練習4
(1)
(2)
(3)
解説4
(1)
10進数に直したときに4の倍数となるようなものを順番に書いていけば法則がわかるかもしれないので書いていこう。
4→100b, 8→1000b, 12→1100b, 16→ 10000b ……
と書いてくと、00で終わるような文字列は必ず4の倍数となることがわかるだろう。
00で終わるような文字列は下のような有限オートマトンで記述することができるので正則である。
(2)
3の倍数は4の倍数ような単純な規則とはならない。なので正則ではないと思ったそこのあなた…
どんな数(範囲は無限大)でも3で割ったあまりは0か1か2の3通りしかありませんよね。0,1,2の3通りは当然有限個なので有限オートマトンを書くことができ、正則なのです。
ということで、とある2進数を3で割ったあまりが0のとき、1のとき、2のときの3つに場合分けをする。
また、それぞれの状態(あまりが0,1,2それぞれの2進数の状態)に0を加えたとき、1を加えたときに3で割ったあまりがどうなるかを考える。
ある2進数の右端に0を加えると、その2進数の値は2倍に、1を加えると2倍+1されることに注意すると以下のように表せる*2。
(i) ある2進数を3で割ったときのあまりが0のとき
2進数は
0を加える:値は2倍
1を加える:値は2倍+1
(ii) ある2進数を3で割ったときのあまりが1のとき
2進数は
0を加える:値は2倍
1を加える:値は2倍+1
(iii) ある2進数を3で割ったときのあまりが2のとき
2進数は
0を加える:値は2倍
1を加える:値は2倍+1
それぞれの2進数のあまりが0,1,2のときに0を加えたとき、1を加えたときのあまりを表にし、最初に1が来た場合と0が来た場合を場合分けすると下のような状態遷移図で表せる。
(3)
10進数に直したときに
とすると、最初に1が来てその後ずっと0の文字列を10進数になおすと
パターン5 文字数が有限以下/以上の場合
最後に文字列に制限がかかったバージョンも練習してみましょう。
文字数制限をかけることによって言語が受理するかどうかが変化することがよくあります。では、5問ほど練習してみましょう。
練習5
つぎの(1)〜(3)の言語
(1)
(2)
(3)
(4)
(5)
解答5
(1)
解答:正則である
理由:この言語の受理非受理を確認するためには、
しかし今回は
(2)
解答:正則ではない
(1)に似てるが、この言語の受理非受理を確認するためには、
なので100文字以上(無限)の
(3)
解答:正則である
(2)に似ているが、この言語の受理非受理を確認するためには
なので
よって正則である。
(4)
解答:正則である
よって正則。
(5)
解答:正則である
一見100文字以上(つまり無限大まで含まれる)の制限がついてるため正則ではないように見えるが実際は100文字未満か以上かを判定するだけでよいので100文字分あるかどうかを記憶させればよい。(100文字以上は必ず受理なので記憶させる必要なし)
よって正則。
さいごに
今回はオートマトンと言語理論における正則判定の練習、正則だった場合の決定性オートマトン(最小状態の)、および正則でなかった場合の証明練習についてまとめました。
基本的にオートマトンは理論さえ知ってしまえばあとはパズルゲーに近いので、ひたすら練習して頭を柔らかくしていきましょう!
今回でしばらくオートマトンと言語理論の記事はお休みします。
関連広告・スポンサードリンク