正規言語
正規言語(せいきげんご)または正則言語(せいそくげんご)は、以下に示す性質(いずれも等価)を満たす形式言語である。
決定性有限オートマトンによって受理可能
非決定性有限オートマトンによって受理可能
正規表現で記述可能
正規文法から生成可能
読みとり専用チューリングマシンで受理可能