オタクof数理の共同ブログ

京大情報学科数理工学コースの学生4人による共同ブログです

正則言語

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

正則言語

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

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

正則言語の閉包性

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

  • \overline{L_1}は正則言語
  • L_1\cup L_2は正則言語
  • L_1\cap 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}}がド・モルガンの公式から分かるので上に証明したことから正則言語の積集合もまた正則言語であることが分かります.

正則言語の閉包性の証明には正則表現の4つの表現方法をうまく活用することで簡単に示すことが出来ます.

正則言語の性質

正則言語の性質としてPumping Lemmaがあります.

Pumping Lemma

Lを正則言語とします. あるn\in\mathbb{N}で, 長さn以上のすべてのw\in Lに対してw=xyzと分解します. そうするとx,y,zについて

  • y\ne\varepsilon
  • |xy|\le n
  • k\in\mathbb{Z}_{\ge 0}に対して, xy^kz\in L

です.

Pumping Lemmaは正則言語そのものよりも考える言語が正則言語で無いことを示す事によく使われます. 例えばL_{01}=\{0^i1^i|i\ge 1\}が正則言語でないことはPumping Lemmaの逆から示されます.


それでは