正規言語(RL)
有限オートマトン(finite automaton)が受理する言語として定義される形式言語のことをいう
次のようにも呼ぶことがある
正則言語 regular language, RL
有限状態言語 finite state language
記法としては、有限オートマトン$ Mが受理する入力記号列全体の集合を$ L(M)と表し、Mが受理する言語(language accepted by M)あるいはMが認識する言語(language recognized by M)という
Wikipedia
In theoretical computer science and formal language theory, a regular language (also called a rational language)12 is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expressions engines, which are augmented with features that allow recognition of non-regular languages).
Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem3 (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars.
これを見ると、「正規表現によって定義できる言語」という定義も与えられている
ただしここでいう正規表現は厳格な狭い意味であり、実用されるいわゆる正規表現はより表現力が高いため正規言語ではないものを認識できるということらしい
有限オートマトンで認識できる言語であることにも言及されていて、この2つの定義の等価性がKleeneの定理として知られている