正則言語

こんにちは, よねすけです.

正則言語とは正則表現で表される言語のことです. 同値な表現方法として以下があります.

すなわち上の4つの表現方法はいずれも能力として等価であるということです.

正則言語には閉包性という性質があります. 具体的には正則言語 $L_1,L_2$ について,

などです. それぞれ証明しましょう.

$L_1$ は正則言語なのである ${\rm DFA} A$ で認識される言語です. $A=(Q,\sum,\delta,q_0,F)$ として, 次のオートマトン $B$ を考えます. $B=(Q,\sum,\delta,q_0,Q-F)$ とすると, 受理状態と非受理状態が綺麗に入れ替わることが分かるので $L(B)=\overline{L_1}$ となり, $\overline{L_1}$ も ${\rm DFA}$ で受理できることが分かりました. よって $\overline{L_1}$ も正則言語です.
$L_1,L_2$ は正則言語なのである正則表現 $R_1,R_2$ を用いて, $L_1=L(R_1),L_2=L(R_2)$ と書くことが出来ます. このとき正則表現の書き方から $L(R_1+R_2)$ は $L_1\cup L_2$ と一致することが分かります. よって正則言語の和集合もまた正則表現になることが分かります.
$L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$ がド・モルガンの公式から分かるので上に証明したことから正則言語の積集合もまた正則言語であることが分かります.