1-3.正則集合 その2
定義:Σ上の正則集合
- 空集合φは正則集合
- a∈Σ ⇒ {a}は正則集合
- X,Y⊆Σ*が正則集合 ⇒ X∪Y,XY,X*は正則集合
いかにも帰納法が使えそうな感じの定義である。あれ? ε∈Σ*だけど、文字としてΣに含まれているわけではないから、{ε}は正則集合じゃないんだね…。
正則集合を定義するのに用いた三つの演算∪,・,*を正則演算、正則集合を先の定義(1)~(3)どおりにφと{a}(a∈Σ)と正則演算をつかって表したものをその集合の正則表現とよぶ。
例:{「あ」}、{「い」}は正則集合だから、あ*={ε,あ,ああ,あああ,…}、い*={ε,い,いい,いいい,…}も正則集合で、(あ*・い*)∪(い*・あ*)∪…={ε,あ,い,あい,いあ,ああい,…}={あ,い}*も正則集合。
くっつけたりならべかえたり、ふつうの操作で作れる集合は正則と考えてよさそう。ところが、無理数同様に濃度は正則でない集合の方がはるかに濃い(多い)。
[…] 省略しすぎ? ま、まあ、それよりも「正則でない集合」がどんなものか、前から気になっている。 定義によれば、正則集合の積集合 X∩Y は正則集合と定められていない。しかし、単純に{a,b,c,d}∩{c,d,e,f}={c,d} としたところで、これは正則集合の和集合{c}∪{d}と同じなのでやはり正則集合になってしまう。何か反例はないかな…。 […]