正则表达式
用法 泵定理(pumping lemma):判断一个语言不是正则语言，通常使用反证法（泵引理是RL语言的必要条件） 原理 设\( L \) 是一个RL，则存在仅依赖于\( L \)的正整数\( P \) 对于\( \forall w \in L \)， 如果\( |w| \ge P \)，则存在\( x, y, z \in \Sigma^{*} \) 满足\( w = xyz \)，同时有: (1) \( |xy| \le P \) (2) \( |y| \ge 1\) (3) \( \forall i \in N{0}，xy{i}
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=