正規言語

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

[編集] 文字セットについての正規言語

文字セット Σ 上の正規言語の集合は以下のように再帰的に定義される。

空の言語 0 は正規言語である。
空文字列言語 { ε } は正規言語である。
a ∈ Σ である各 a について、それだけを含む言語 { a } は正規言語である。
A と B が正規言語であるとき、A ∪ B（和集合）も A • B（結合）も A*（クリーネ閉包）も正規言語である。
それ以外の Σ 上の言語は正規言語ではない。

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

[編集] 閉包属性

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

[編集] ある言語が正規言語であるかどうかの判断基準

チョムスキー階層での正規言語の位置によれば、正規言語は文脈自由言語に含まれる。その逆は真ではない。例えば、同じ個数の a と b を含む文字列から成る言語は文脈自由言語ではあるが、正規言語ではない。このような言語が正規言語ではないことを証明するには、Myhill-Nerodeの定理か反復補題 (Pumping Lemma) を使う。

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

もう一つの方法として、L が Σ 上の言語であるとき、Σ* 上の同値関係 ~ を次のように定義する。

$x \sim y :\Leftrightarrow \forall z \in \Sigma^* : xz \in L \leftrightarrow yx \in L$