正则语言

• 所有的有限语言都是正则的。
• 字母表{a, b}上包含偶数个a的所有字符串构成的语言是正则的。
• 字母表{a, b}上取若干个a后紧跟若干个b形式的所有字符串构成的语言是正则的。

在字母表集合Σ上的正则语言定义如下：

• 空集合Ø是正则语言
• 只包含一个空串的语言{ε}是正则语言
• 对所有${\displaystyle a\in \Sigma }$ ，{a}是正则语言
• 若A, B是正则语言，则${\displaystyle A\cdot B,A\bigcup B,A^{*}}$ (kleene星号)都是正则语言
• 除此之外都不是正则语言

如果一个语言不是正则语言，它需要一个存储器至少是Ω(log log n)的自动机才能辨认。换句话说，DSPACE(o(log log n))等于所有正则语言的集合。实际上，大部分的非正则语言需要至少O(log n)的空间。

这里语言的运算参见条目形式语言。

• 正则语言的交、并、差、补运算得到的语言仍然是正则语言；
• 两个正则语言连接（把第一个语言的所有字符串同第二个语言的所有字符串连接起来）后得到的语言仍然是正则语言；
• 正则语言闭包运算后得到的语言仍然是正则语言；
• 正则语言的每个字符串转置后得到的语言仍然是正则语言；
• 正则语言被任意语言的字符串商（左商或右商）后得到的语言仍然是正则语言。
• 正则语言字符串代换后得到的语言仍然是正则语言。
• 与正则语言字符串同态或逆同态的语言仍然是正则语言。

正则语言也可以以纯粹代数的方式来定义。

Σ是一个有穷的字母表，Σ*是Σ上的自由幺半群，Σ*构成了Σ上的所有字符串。令M为一个有限幺半群，映射f : Σ* -> M为一个幺半群同态，集合S是M的一个子集，于是S的逆同态象f ^-1(S)是正规的。每一个正则语言都可以依这种方式来定义。

另外一种定义方式借助于一个等价关系。

取L为Σ*的任意子集，定义如下的Σ*上的等价关系~ (叫做“语法关系”)： u ~ v，即对Σ*中所有的的字符串w有uw在L中当且仅当vw在L中。于是对正则语言有下面的结论：语言L是正规的当且仅当关系~的等价类的数量是有限的（其证明在条目语法幺半群中）。在此情况下，等价类的数量就是接受语言L的最小确定有限状态自动机的状态数。

• 形式语言
• 有限状态自动机
• 正则表达式
• 正则文法
• 乔姆斯基体系

• Michael Sipser（英语：Michael Sipser）. Introduction to the Theory of Computation. PWS Publishing. 1997.   Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.