1 正规定义
术语
| TERM | EXPLANATION |
|---|---|
| 字母表 | 符号的有限集合 |
| 串 | 字母表符号的有穷序列 |
| 空串 | 长度为 0 的特殊串，用 \varepsilon 表示 |
| 语言 | 字母表上的一个串集 |
| 句子或字 | 语言的一个元素 |
字母表上的运算
（1）连接：x 和 y 的连接记作 xy。
（2）幂：多次连接，s^i=s^{i-1}s。
语言上的运算
假设 L,M 都是语言，则
（1）并：L\cup M=\{s|s\in L\text{ or }s\in M\}；
（2）连接：LM=\{st|s\in L\text{ and }t\in M\}；
（3）闭包：L^*=\cup_{i=0}^\infty L^i；
（4）正闭包：L^+=\cup_{i=1}^\infty L^i。
正规式
一个正规式 r 表示一个语言 L(r)，规则如下。
（Ⅰ）\varepsilon 是正规式，表示语言 \{\varepsilon\}；
（Ⅱ）若 a\in \Sigma，则 a 是正规式，表示语言 \{a\}；
（Ⅲ）若 r,s 是正规式，则
\begin{aligned}
(r)|(s)&→L(r)|L(s)\newline
(r)(s)&→L(r)L(s)\newline
(r)^*&→(L(r))^*\newline
(r)&→L(r)
\end{aligned}
正规式表示的语言叫正规语言（正规集）。
如果规定一些运算优先级和结合性，则可以省去一些正规式中不必要的括号。
正规定义
正规定义形式： $$ \begin{aligned} &d_1→r_1\newline &\cdots\newline &d_n→r_n \end{aligned} $$ 这里面 d_i 是各不相同的名字（不是符号），每个 r_i 是 \Sigma\cup\{d_1,...,d_{i-1}\} 上的正规式。
例子
\begin{aligned}
&\boldsymbol{letter\_}→A|B|...|Z|a|b|...|z|\_\newline
&\boldsymbol{digit}→0|1|...|9\newline
&\boldsymbol{id}→\boldsymbol{letter\_}(\boldsymbol{letter\_}|\boldsymbol{digit})^*
\end{aligned}