最新消息: 电脑我帮您提供丰富的电脑知识,编程学习,软件下载,win7系统下载。

正则集与正则表达式辨析

互联网 admin 5浏览 0评论

正则集与正则表达式辨析

文章目录

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

正则集

  • 正则集是一种字符串的集合,也就是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的详细规定。

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

发布评论

评论列表 (0)

  1. 暂无评论