从正则表达式到NFA

正则表达式 定义 : 正则表达式可以描述所有通过对某个字母表上的符号应用并、连接、闭包运算而得到的语言;可以用正则表达式定义的语言叫做正则集合 性质 : 如果两个正则表达式 r 和 s 表示同样的语言,则称 r 和 s等价 遵循一些代数性质 定律 描述 \( r | s = s | r \) | 是可以交换 \( r|(s| »

子集构造法

概念 首先介绍一下 有限自动机 FA (Finite Automate)的概念,形式上它是一个五元组 \( (S, \sum, \delta, s_0, S_A) \) \( S \) 是识别器的有限状态集,以及一个错误状态\( S_e\) \( \sum \)是识别器使用的有限字母表。通常,\( \sum \) 是转移图中边的标签合集 \( \delta( »