正規言語
アルファベット
$ \Sigma
に対して
正規言語
は以下
空集合
$ \empty
空文字
$ \varepsilon
だけで構成された単集合
$ \{\varepsilon\}
$ a \in \Sigma
で
$ a
の単集合
$ \{a\}
$ A,B
が正規言語なら和集合
$ A + B
,結合
$ A \cdot B
,
クリーネ閉包
$ A^*
それ以外は,正規言語ではない
次
決定性有限オートマトン
または
非決定性有限オートマトン
で受理可能
正規表現
で記述可能
正規文法
で生成可能