正则语言的定义#

正则语言是在有限字母表 $\Sigma$ 上的一个集合，其中包含的元素是所有能被一个正则表达式/DFA/NFA识别的字符串，正则语言是$\Sigma^*$的一个子集

正则表达式的定义#

正则表达式是一个字符串，使用特定的语法规则来描述一个正则语言。正则表达式和DFA、NFA之间是等价的，即它们识别的正则语言是相同的

正则表达式由以下基本元素组成，且以下每个元素本身也是一个正则表达式：

• 空集：表示一个不包含任何字符串的语言，通常用符号 $\emptyset$ 表示
• 空字符串：表示一个只包含空字符串的语言，通常用符号 $\epsilon$ 表示
• 单个符号：对于每个输入符号 $a \in \Sigma$，表示一个只包含字符串 $a$ 的语言
• 连接：如果 $R$ 和 $S$ 是正则表达式，那么 $RS$ 表示连接操作，表示由 $R$ 中的字符串连接 $S$ 中的字符串组成的语言，或多次连接，例如 $R^n$ 表示由 $R$ 中的字符串连接 $n$ 次组成的语言，$R^0=\{\epsilon\}$
• 选择：如果 $R$ 和 $S$ 是正则表达式，那么 $R|S$ 表示选择操作，表示由 $R$ 中的字符串或 $S$ 中的字符串组成的语言
• 闭包：如果 $R$ 是一个正则表达式，那么 $R^*$ 表示闭包操作，表示由 $R$ 中的字符串重复零次或多次组成的语言

一个正则表达式通过有限次上述操作后生成的仍然是一个正则表达式，因此正则表达式可以递归定义

TIP

正闭包：$R^+$ 表示由 $R$ 中的字符串重复一次或多次组成的语言，即 $R^+ = RR^*$

克林闭包：$R^*$ 表示由 $R$ 中的字符串重复零次或多次组成的语言，即 $R^* = \{\epsilon\} \cup R^+$

运算顺序：括号 > 闭包 > 连接 > 选择

例子#

设计一个正则表达式匹配所有包含110但不能包含111的二进制字符串

可以使用以下正则表达式：