-形式语言、自动机与正则表达式¶
啃啃铎铎的书
一、语言¶
字母表（alphabet）指的是一个有限的非空符号集 \(\Sigma\)，其中元素称为 字母。
由字母表 \(\Sigma\) 生成的有限长度序列全体写作 \(\Sigma^*\)，其中元素称为 \(\Sigma\) 上的 词 或 串，其中的空序列称为 空串（empty string） 或 零串（null string），习惯上用 \(\lambda\) 或 \(\varepsilon\) 表示，并使用 \(\Lambda\) 表示集合 \(\{\lambda\}\)。
设 \(w_1 = s_1s_2\cdots s_n\) 和 \(w_2 = t_1t_2\cdots t_m\) 都是字母表 \(\Sigma\) 上的串，则 \(w_1\) 和 \(w_2\) 的 连接（concatenation）定义为 \(s_1s_2\cdots s_nt_1t_2\cdots t_m\)，记作 \(w_1\circ w_2\) 或 \(w_1w_2\)。\(\circ\) 称为 \(\Sigma^*\) 上的 连接运算。
设 \(\Sigma\) 为优先字母表，\(\Sigma^*\) 的任一个子集 \(L\) 都成为 \(\Sigma\) 上的一个 语言（language），语言的元素称为 句子。
设 \(L_1\) 和 \(L_2\) 是有限字母表 \(\Sigma\) 上的两个语言，则可定义 \(L_1\) 与 \(L_2\) 的 连接 为 $$ {\alpha\beta | \alpha \in L_1, \beta\in L_2} $$ 记作 \(L_1 \circ L_2\) 或 \(L_1L_2\)。
设 \(L\) 是有限字母表 \(\Sigma\) 上的语言，定义 \(L\) 的 \(n\) 次幂 \(L^n\) 为 $$ \begin{align} L^0 &= \Lambda\ L^n &= L^{n-1} \circ L, n \geq 1 \end{align} $$ 定义 \(L\) 的 正闭包 为 $$ L^+ = L^1 \cup L^2 \cup L^3 \cup \cdots $$ 定义 \(L\) 的 克林星闭包 为 $$ L^* = \Lambda \cup L^+ = L^0 \cup L^1 \cup L^2 \cup L^3 \cup \cdots $$
二、文法¶
咕