正規言語のソースを表示

'''正規言語'''（せいきげんご）または'''正則言語'''（せいそくげんご）は、以下に示す性質（いずれも等価）を満たす[[形式言語]]である。

*[[決定性有限オートマトン]]によって受理可能
*[[非決定性有限オートマトン]]によって受理可能
*[[正規表現]]で記述可能
*[[正規文法]]から生成可能
*読みとり専用[[チューリングマシン]]で受理可能

== 定義 ==
文字セット &Sigma; 上の正規言語の集合は以下のように再帰的に定義される。
* 空の言語 0 は正規言語である。
* 空文字列言語 { &epsilon; } は正規言語である。
* ''a'' &isin; &Sigma; である各 ''a'' について、それだけを含む[[単集合]]言語 { ''a'' } は正規言語である。
* ''A'' と ''B'' が正規言語であるとき、''A'' &cup; ''B''（和集合）も ''A'' &bull; ''B''（結合）も ''A''*（[[クリーネ閉包]]）も正規言語である<ref>つまり[[正規演算]]に[[閉じている]]。</ref>。
* それ以外の &Sigma; 上の言語は正規言語ではない。

有限の文字列から構成される言語は全て正規言語である。その他の典型的な例としては、文字セット {''a'', ''b''} を使った文字列のうち、偶数個の ''a'' を含む文字列の集まりは正規言語であるし、任意個数の ''a'' の後に任意個数の ''b'' が続く文字列で構成される言語も正規言語である。

== 閉包属性 ==
正規言語に対して、和集合、積集合、差集合といった演算を施した結果も正規言語である。正規言語の補集合（文字セットから生成される全文字列を全体集合とする）も正規言語である。正規言語の文字列を全て逆転させたものも正規言語である。正規言語の連結（ふたつの言語に含まれる文字列をあらゆる組み合わせで連結した文字列の集合）をしたものも正規言語である。「シャッフル」をふたつの正規言語に施した結果も正規言語である。正規言語と任意の言語の商集合も正規言語である。個々の操作の具体的意味については[[形式言語#定義]]を参照されたい。

== ある言語が正規言語であるかどうかの判断基準 ==
[[チョムスキー階層]]での正規言語の位置によれば、正規言語は[[文脈自由言語]]の[[部分集合|真部分集合]]である。すなわち、正規言語は文脈自由言語に含まれる一方、その逆は真ではない。

例えば、同じ個数の ''a'' と ''b'' を含む文字列から成る言語は文脈自由言語ではあるが、正規言語ではない。このような言語が正規言語ではないことを証明するには、[[マイヒル-ネローデの定理]]か[[正規言語の反復補題|反復補題]] (pumping lemma) を使う。

正規言語を代数学的に定義するには、二つの方法がある。&Sigma; を有限のアルファベットとし、&Sigma;* を &Sigma; 上の[[自由モノイド]]（&Sigma; によって作られる記号列全て）とすると、''f'' : &Sigma;* &rarr; ''M'' は[[モノイド同型]]となる。ただしここで ''M'' は''有限''のモノイドである。そして、''S'' を ''M'' の部分集合とすると、''f''<sup>&minus;1</sup>(''S'') は正規言語となる。任意の正規言語はこのようにして構成することができる。

もう一つの方法として、''L'' が &Sigma; 上の言語であるとき、&Sigma;* 上の[[同値関係]] ~ を次のように定義する。
:<math>x \sim y :\Leftrightarrow \forall z \in \Sigma^* : xz \in L \leftrightarrow yz \in L</math>
すると、''L'' が正規言語であることは、同値関係 ~ の作る同値類の指標（濃度）が有限であることと[[同値]]になる。そして、同値類の指標は ''L'' を受理する最小の決定性有限オートマトンの状態の個数に一致する。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

{{デフォルトソート:せいきけんこ}}
[[Category:有限オートマトン]]
[[Category:形式言語]]
[[Category:数学に関する記事]]