NFA
正则表达式 定义 : 正则表达式可以描述所有通过对某个字母表上的符号应用并、连接、闭包运算而得到的语言；可以用正则表达式定义的语言叫做正则集合 性质 : 如果两个正则表达式 r 和 s 表示同样的语言，则称 r 和 s等价 遵循一些代数性质 定律 描述 \( r | s = s | r \) | 是可以交换 \( r|(s|t) = (r|s)|t \) | 是可结合的 \( r(st) = (rs)t \) 连接是可结合的 \( r(s|t)=rs|rt \)；\( (s|t)r=sr|tr \) 连接对|是可分配的 \( \epsilon r=
自动机
概念 首先介绍一下 有限自动机 FA （Finite Automate）的概念，形式上它是一个五元组 \( (S, \sum, \delta, s_0, S_A) \) 1. \( S \) 是识别器的有限状态集，以及一个错误状态\( S_e\) 2. \( \sum \)是识别器使用的有限字母表。通常，\( \sum \) 是转移图中边的标签合集 3. \( \delta(s, c) \)是识别器的转移函数。它将每个状态 \(s \in S \)和每个字符\(c \in \sum \)映射到下一个状态。在状态\( s_i \)遇到输入字符\(c\)，FA将采取\(s_i \rightarrow^