ある言語が正規言語であるかどうかの判断基準
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/07 15:06 UTC 版)
「正規言語」の記事における「ある言語が正規言語であるかどうかの判断基準」の解説
チョムスキー階層での正規言語の位置によれば、正規言語は文脈自由言語の真部分集合である。すなわち、正規言語は文脈自由言語に含まれる一方、その逆は真ではない。 例えば、同じ個数の a と b を含む文字列から成る言語は文脈自由言語ではあるが、正規言語ではない。このような言語が正規言語ではないことを証明するには、マイヒル-ネローデの定理か反復補題 (Pumping Lemma) を使う。 正規言語を代数学的に定義するには、二つの方法がある。Σ を有限のアルファベットとし、Σ* を Σ 上の自由モノイド（Σ によって作られる記号列全て）とすると、f : Σ* → M はモノイド同型となる。ただしここで M は有限のモノイドである。そして、S を M の部分集合とすると、f−1(S) は正規言語となる。任意の正規言語はこのようにして構成することができる。 もう一つの方法として、L が Σ 上の言語であるとき、Σ* 上の同値関係 ~ を次のように定義する。 x ∼ y :⇔ ∀ z ∈ Σ ∗ : x z ∈ L ↔ y x ∈ L {\displaystyle x\sim y:\Leftrightarrow \forall z\in \Sigma ^{*}:xz\in L\leftrightarrow yx\in L} すると、L が正規言語であることは、同値関係 ~ の作る同値類の指標（濃度）が有限であることと同値になる。そして、同値類の指標は L を受理する最小の決定性有限オートマトンの状態の個数に一致する。
※この「ある言語が正規言語であるかどうかの判断基準」の解説は、「正規言語」の解説の一部です。
「ある言語が正規言語であるかどうかの判断基準」を含む「正規言語」の記事については、「正規言語」の概要を参照ください。
- ある言語が正規言語であるかどうかの判断基準のページへのリンク
