有限オートマトン2-3.正則集合と有限オートマトン(2) その2

 既述のLijkのjに関する帰納法によりLijkが正則集合であることが示される。

定理2.3
有限オートマトンの受理集合は正則集合である。

 省略しすぎ?
 ま、まあ、それよりも「正則でない集合」がどんなものか、前から気になっている。
 定義によれば、正則集合の積集合 X∩Y は正則集合と定められていない。しかし、単純に{a,b,c,d}∩{c,d,e,f}={c,d} としたところで、これは正則集合の和集合{c}∪{d}と同じなのでやはり正則集合になってしまう。何か反例はないかな…。

正則集合の無限個の和は必ずしも正則集合ではない。
問1.18(3) X={anbn|n=0,1,2,…}は正則集合でないことを示せ。
正則集合が正則演算のほかに反転、除算、正則代入などに関して閉じたクラスをなすことを見てきたが、その他の演算についてはどうだろうか。

 ヒントはこのあたりだろうか。


Want to Leave a Reply?