正規言語
文字セット Σ 上の正規言語の集合は以下のように再帰的に定義される。
空の言語 0 は正規言語である。
空文字列言語 { ε } は正規言語である。
a ∈ Σ である各 a について、それだけを含む単集合言語 { a } は正規言語である。
A と B が正規言語であるとき、A ∪ B(和集合)も A • B(結合)も A*(クリーネ閉包)も正規言語である。
それ以外の Σ 上の言語は正規言語ではない。
有限の文字列から構成される言語は全て正規言語である。その他の典型的な例としては、文字セット {a, b} を使った文字列のうち、偶数個の a を含む文字列の集まりは正規言語であるし、任意個数の a の後に任意個数の b が続く文字列で構成される言語も正規言語である。