- この関係を考えるときに、「正規言語の任意の部分集合は正規言語といえるのだろうか」ということが気になっている。
- これがいえるからといって、演習問題が解けるとは限らないのだが、なんだか気になる。
- で、ちょっと考えてみる。
- まず、有限集合である言語は、全て正規言語ではないか、ということ。
- これはその有限の文字列を全て分岐して試すようなNFAを構成できるので真。
- そうすると、部分集合が無限集合のときだけ考えればよいことになる。
- 無限集合である正規言語を考えるとき、その無限を生み出しているのは正規表現でいうとスター演算のみであることに気付く。
- Σ={0}, L = Σ* = {ε, 0, 00, 000, ...}として、0の個数が2^n個のものだけを取り出して言語をなしたとすると、それはどうも正規表現で書けそうにないので偽なのだろう。
- ちょっと演習問題まで考えてみる。
- たしか、「A <=m BでBが正規言語のときに、Aが正規言語といえるかどうか」ということだったはず。(問題を見返す元気もない。。。)
- ここで、w∈A <=> f(w)∈B だったはず。
- 上で見た例を適用するとどうなるか。
- L(B) = Σ*とする。
- L(A) = {w | wは0以外の文字を含まない文字列。ただし0の個数が2^nである。ここでnは自然数}とする。
- fは、「文字列に0以外を含むなら、入力文字に写像。文字列が0以外を含まず長さが2^nならBの該当要素に写像。これら以外なら、1に写像」とするとする。
- そうするとfは帰着写像になっている。
- これはBが正規言語だが、それへの帰着写像が存在するAは正規言語ではない。
- これで反例をしめせた。
- 本当か?
- 精査する余力がない。。。
- 次回、精査することにする。
こつこつ。
0 件のコメント:
コメントを投稿