正則言語が
- 集合和
- 補集合
- 共通部分
- 集合差
- 連接
- 閉包
の演算に関して閉じているということを示した。証明自体は簡単。これによりなかなかうれしい性質が得られる。証明のところでは、(NFAではなく)DFAの性質を使っているところがあったりもする。が、前回NFAはDFAに等価で、変換する方法も分かっていると証明したのであんまり問題ない。
クリーネ閉包とはか筑波で受けた自然言語処理の授業でなんか聞いたことがある気がする。表現できる言語のクラスの付近で。計算理論IIとかで出てくるのかな。割と好きなので受けようと思う。
で、正則言語の性質は分かったんだけど、人間が分かりやすい形でこれを理解したい。これが正則表現。いわゆる正規表現。正規表現の定義が色々されるわけだけど、来週にこれがNFAとDFAと等価なモデルであることが証明されるらしい。wktk。正確に書くと
- DFAが受理する言語
- NFAが受理する言語
- 正則表現が表す言語
は全て正則言語である、ということ。
あと、そろそろ
- (NFA|DFA|正規表現)で何が表現できないのか
- 表現できないものがあるとするとどういうモデルなら表現可能なのか
に興味湧いてきた。理論的な限界点って付近か。
