正規言語
チョムスキー階層での正規言語の位置によれば、正規言語は文脈自由言語の真部分集合である。すなわち、正規言語は文脈自由言語に含まれる一方、その逆は真ではない。
例えば、同じ個数の a と b を含む文字列から成る言語は文脈自由言語ではあるが、正規言語ではない。このような言語が正規言語ではないことを証明するには、マイヒル-ネローデの定理か反復補題 (pumping lemma) を使う。
正規言語を代数学的に定義するには、二つの方法がある。Σ を有限のアルファベットとし、Σ* を Σ 上の自由モノイド(Σ によって作られる記号列全て)とすると、f : Σ* → M はモノイド同型となる。ただしここで M は有限のモノイドである。そして、S を M の部分集合とすると、f(S) は正規言語となる。任意の正規言語はこのようにして構成することができる。
もう一つの方法として、L が Σ 上の言語であるとき、Σ* 上の同値関係 ~ を次のように定義する。
x ∼ y :⇔ ∀ z ∈ Σ ∗ : x z ∈ L ↔ y z ∈ L {\displaystyle x\sim y:\Leftrightarrow \forall z\in \Sigma ^{*}:xz\in L\leftrightarrow yz\in L}
すると、L が正規言語であることは、同値関係 ~ の作る同値類の指標(濃度)が有限であることと同値になる。そして、同値類の指標は L を受理する最小の決定性有限オートマトンの状態の個数に一致する。