正则表达式

正则表达式将形式语言定义为有限字母表上的字符串集合。令 表示一个选定的字母表。那么 是一个正则表达式，表示空集，而 是一个正则表达式，表示包含空字符串作为其唯一元素的集合。

如果 , 那么 是一个正则表达式，表示仅包含字符串 的集合。如果 和 是正则表达式，分别表示集合 和 ，那么

1. 是一个正则表达式，表示集合 ，其中 表示并集。

2. 是一个正则表达式，表示所有字符串 和 的连接所形成的集合，其中 且 。

3. 是一个正则表达式，表示 的闭包，即由 中的字符串进行零次或多次连接所形成的集合。

由正则表达式定义的集合称为正则集，一个集合是正则的当且仅当它由右线性文法定义。