正规语言

正规语言的定义

设∑为有穷字母表，∑*为其Kleene闭包（见作用代数）。那么称字符串集L∈∑*为正规语言，当且仅当满足下列条件之一：

1.L可以被一个确定有穷自动机识别；

2.L可以被一个非确定有穷自动机识别；

3.L可以用正则表达式表达；

4.L可以用正则文法生成；

5.L可以由前缀文法生成；

正规语言的性质

一、封闭性

1.正规语言的交、并、差、补运算得到的语言仍然是正则语言；

2.两个正规语言连接（把第一个语言的所有字符串同第二个语言的所有字符串连接起来）后得到的语言仍然是正规语言；

3.正规语言闭包运算后得到的语言仍然是正规语言；

4.正规语言的每个字符串转置后得到的语言仍然是正规语言；

5.正规语言被任意语言的字符串商（左商或右商)后得到的语言仍然是正规语言；

6.正规语言字符串代换后得到的语言仍然是正规语言；

7.与正规语言字符串同态或逆同态的语言仍然是正规语言；

二、判定准则

1.判定一个语言不是正则语言通常使用泵引理，或者其加强形式；

2.要判断一个语言是正则语言，一般方法是构造一个识别该语言的有穷自动机或正则表达式。也可以通过迈希尔－尼罗德定理所确定的充要条件来证明；

正则语言的应用

由于正则语言可以用有穷自动机识别，所以在进行字符串匹配时可以设计一个无回溯的分析程序。这样就可以使得字符串匹配可以在O(n)时间内完成，而且很容易编程实现。（正则语言在字符串匹配中的应用可以参见词条：正则表达式）