正则集与正则表达式辨析

文章目录

• 正则集
• 正则表达式
• • 解析正则表达式的定义

正则集

• 正则集是一种字符串的集合，也就是T*的子集。
• 本质上，正则集是一种语言，集合的所有元素满足当且仅当可以被某种正则表达式表示。

正则表达式

• 正则表达式本身是一种元语言，是一种表示语言的语言。
• 即，正则集是一种语言，正则表达式是一种表达正则集的元语言
• 正则表达式的定义：
• 可以将正则表达式视为一种映射的key，而正则表达式表达的语言视为该映射的value，即一个map = (key, value) = (正则表达式，正则集）。而一个字符串w可以被一个正则表达式表示，即存在一个map，使得 map(某个正则表达式）= w
• 那么这个map的规则具体是什么呢？正则表达式的定义目的就是给出map的具体规则。

解析正则表达式的定义

• 基础：定义正则表达式和正则集的映射关系：
  • 正则表达式 => 正则集
  • a => {a}
  • ϵ = > { ϵ } \epsilon => \{\epsilon\} ϵ=>{ϵ}
  • 空集 => 空集
• 归纳：定义正则表达式的运算和正则集的运算的映射关系：
  • 正则表达式的运算 => 正则集的运算
  • a* => {a}内的元素的任意次连接
    • 若正则表达式w => {a}，则w* => { ϵ \epsilon ϵ, a, aa, aaa, aaaa, …}
  • a+b => { a } ∪ { b } \{a\} \cup \{b\} {a}∪{b}
    • 若正则表达式w1 => {a, b}，正则表达式w2 => {ab，ba}，则
    • w1+w2 => {a, b, ab, ba}
  • ab => {a}的元素和{b}的元素分别连接
    • 若正则表达式w1 => {a, b}，正则表达式w2 => {c, d}，则
    • w1w2 => {ac, ad, bc, bd}
• 现在有正则表达式w1，w2，根据基础，分别有map(w1)= 集合 t1，map(w2)= 集合 t2。
• 对w1和w2进行有限次运算，即operation(w1, w2)，根据归纳，有map(operation) = operation’，故operation(w1, w2) = operation’(t1, t2) = t3
• 给定了基础的正则表达式，就可以通过map规则得到映射后的基础的正则集；通过正则表达式的运算，得到新的正则表达式，通过map规则映射运算，就可以得到正则集的运算，从而得到新的正则表达式对应的新的正则集。
• 故，只有在前提：
  • 给定基础正则表达式
  • 给定map规则
  • 得到基础正则集
• 通过归纳得到的式子才是正则表达式和正则集。
• 上述的基础和归纳就是map的详细规定。

同一个正则表达式一定可以得到唯一的正则集，同一个正则集可能对应不同的正则表达式。

正则集与正则表达式辨析

文章目录

• 正则集
• 正则表达式
• • 解析正则表达式的定义

正则集

• 正则集是一种字符串的集合，也就是T*的子集。
• 本质上，正则集是一种语言，集合的所有元素满足当且仅当可以被某种正则表达式表示。

正则表达式

• 正则表达式本身是一种元语言，是一种表示语言的语言。
• 即，正则集是一种语言，正则表达式是一种表达正则集的元语言
• 正则表达式的定义：
• 可以将正则表达式视为一种映射的key，而正则表达式表达的语言视为该映射的value，即一个map = (key, value) = (正则表达式，正则集）。而一个字符串w可以被一个正则表达式表示，即存在一个map，使得 map(某个正则表达式）= w
• 那么这个map的规则具体是什么呢？正则表达式的定义目的就是给出map的具体规则。

解析正则表达式的定义

• 基础：定义正则表达式和正则集的映射关系：
  • 正则表达式 => 正则集
  • a => {a}
  • ϵ = > { ϵ } \epsilon => \{\epsilon\} ϵ=>{ϵ}
  • 空集 => 空集
• 归纳：定义正则表达式的运算和正则集的运算的映射关系：
  • 正则表达式的运算 => 正则集的运算
  • a* => {a}内的元素的任意次连接
    • 若正则表达式w => {a}，则w* => { ϵ \epsilon ϵ, a, aa, aaa, aaaa, …}
  • a+b => { a } ∪ { b } \{a\} \cup \{b\} {a}∪{b}
    • 若正则表达式w1 => {a, b}，正则表达式w2 => {ab，ba}，则
    • w1+w2 => {a, b, ab, ba}
  • ab => {a}的元素和{b}的元素分别连接
    • 若正则表达式w1 => {a, b}，正则表达式w2 => {c, d}，则
    • w1w2 => {ac, ad, bc, bd}
• 现在有正则表达式w1，w2，根据基础，分别有map(w1)= 集合 t1，map(w2)= 集合 t2。
• 对w1和w2进行有限次运算，即operation(w1, w2)，根据归纳，有map(operation) = operation’，故operation(w1, w2) = operation’(t1, t2) = t3
• 给定了基础的正则表达式，就可以通过map规则得到映射后的基础的正则集；通过正则表达式的运算，得到新的正则表达式，通过map规则映射运算，就可以得到正则集的运算，从而得到新的正则表达式对应的新的正则集。
• 故，只有在前提：
  • 给定基础正则表达式
  • 给定map规则
  • 得到基础正则集
• 通过归纳得到的式子才是正则表达式和正则集。
• 上述的基础和归纳就是map的详细规定。

同一个正则表达式一定可以得到唯一的正则集，同一个正则集可能对应不同的正则表达式。