Util - 正则表达式基础


串和语言

字母表

任意有限集合,通常为有穷的符号集合

  • 数字、字母、标点符号
  • {0, 1}, ASCII, Unicode

字母表中符号的有穷序列,空串记为 $\epsilon$

语言

字母表上的串的可数集合

术语

  • 前缀:从串的尾部删除 0 个或多个符号后的串
  • 后缀:从串的头部删除 0 个或多个符号后的串
  • 子串:删除串的某个前缀与某个后缀后得到的串
  • 真X串/缀:不等于原串,也不等于空串的X串/缀
  • 子序列:从原串中删除 0 个或多个符号后的串

运算

  • 串:

    • 连接:$x=\text{fuck},y=\text{you},xy=\text{fuckyou}$
    • 幂运算:$s^0=\epsilon,s^1=s,s^n=s^{n-1}s$
  • 语言:

    运算定义
    L 与 M 并$L\cup M= \{ s\vert s\in L \lor s\in M\}$
    L 与 M 连接$LM=\{ st\vert s\in L\land t\in M\}$
    L 的 Kleene 闭包$L^*=\cup_{i=0}^{\infty}L^i$
    L 的正闭包$L^+=\cup_{i=1}^{\infty}L^i$

正则表达式

基础

  • $\epsilon$ 是一个正则表达式:$L(\epsilon)=\{\epsilon\}$

  • 若 $a$ 为 $\sigma$ 上一符号,$a$ 为正则表达式,$L(a)=\{a\}$

基础运算

  1. 选择:$(r)|(s), L((r)|(s))=L(r)\cup L(s)$

  2. 连接:$(r)(s), L((r)(s))=L(r)L(s)$

  3. 闭包:$(r)^*, L((r)^*)=(L(r))^*$

  4. 括号:$(r), L((r))=L(r)$

优先级:闭包 > 连接 > 选择