正規言語の閉包性

言語 L が正規言語であるのは、この言語を受理するオートマトン A が存在するとき、つまり L(A) = L となるときであり、またそのときに限ります。正規言語が和集合、共通部分、連接、クリーネ閉包の演算について閉じていることを証明します。

演算について閉じている集合

集合 M が演算 ⊗ について閉じているとは、次が成り立つことです。

$$\mathrm{\forall }x,y\in M:x\otimes y\in M$$

例えば、自然数の集合は足し算について閉じています。どの2つの自然数を足しても、和はまた自然数です。一方、自然数の集合は引き算については閉じていません。例えば 7 − 15 = −8 で、−8 は自然数ではないからです。

正規言語の集合がどの演算について閉じているかを証明していきます。証明はどれも構成的です。つまり、得られる言語を受理するオートマトンを実際につくります。