定義:Σ上の正則集合
- 空集合φは正則集合
- a∈Σ ⇒ {a}は正則集合
- X,Y⊆Σ*が正則集合 ⇒ X∪Y,XY,X*は正則集合
いかにも帰納法が使えそうな感じの定義である。あれ? ε∈Σ*だけど、文字としてΣに含まれているわけではないから、{ε}は正則集合じゃないんだね…。
正則集合を定義するのに用いた三つの演算∪,・,*を正則演算、正則集合を先の定義(1)~(3)どおりにφと{a}(a∈Σ)と正則演算をつかって表したものをその集合の正則表現とよぶ。
例:{「あ」}、{「い」}は正則集合だから、あ*={ε,あ,ああ,あああ,…}、い*={ε,い,いい,いいい,…}も正則集合で、(あ*・い*)∪(い*・あ*)∪…={ε,あ,い,あい,いあ,ああい,…}={あ,い}*も正則集合。
くっつけたりならべかえたり、ふつうの操作で作れる集合は正則と考えてよさそう。ところが、無理数同様に濃度は正則でない集合の方がはるかに濃い(多い)。
Pingback: 有限オートマトン2-3.正則集合と有限オートマトン(2) その2 | デザイナーの数学