1-3.正則集合 その2

定義:Σ上の正則集合

  1. 空集合φは正則集合
  2. a∈Σ ⇒ {a}は正則集合
  3. X,Y⊆Σが正則集合 ⇒ X∪Y,XY,Xは正則集合

 いかにも帰納法が使えそうな感じの定義である。あれ? ε∈Σだけど、文字としてΣに含まれているわけではないから、{ε}は正則集合じゃないんだね…。

正則集合を定義するのに用いた三つの演算∪,・,*を正則演算、正則集合を先の定義(1)~(3)どおりにφと{a}(a∈Σ)と正則演算をつかって表したものをその集合の正則表現とよぶ。

 例:{「あ」}、{「い」}は正則集合だから、あ={ε,あ,ああ,あああ,…}、い={ε,い,いい,いいい,…}も正則集合で、(あ・い)∪(い・あ)∪…={ε,あ,い,あい,いあ,ああい,…}={あ,い}も正則集合。
 くっつけたりならべかえたり、ふつうの操作で作れる集合は正則と考えてよさそう。ところが、無理数同様に濃度は正則でない集合の方がはるかに濃い(多い)。

One Response to “1-3.正則集合 その2”

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


Want to Leave a Reply?