详解正则表达式与NFA的转换

详解正则表达式与 NFA 的转换

NFA 是 Non-deterministic Finite state Automata 的缩写。所以先理解 NFA 之前我们先理解 DFA，也就是 deterministic Finite state Automata。

通俗的说， DFA 就是一系列状态的合集 ，关键词是 状态 ！ 我们先写一个关于灯泡的 DFA： （两个圈是终态，我们把「灯泡关闭」的状态当做终态） 简单来说，NFA 就是存在着不确定状态转换的 DFA。

编译原理中正规式（ba|a）*如何转换成NFA

·······状态4 ↑|s | |a b| |s | ↓ 状态1 --ε-->状态2 --ε-->状态3 | ↑ |__|a画图画的很辛苦啊lz。

（把s忽略掉。

两个正则表达式等价的判断

这个相当麻烦，如果你一定要做就要这样做首先把正则表达式转化为，NFA然后NFA-〉DFA-〉SDFA如果两个正则表达式一样，应当具有唯一的SDFA。如果是后面的问题，应当是文法包含，目前没有听说有效解法。

正则表达式

首先我们要了解正则表达式是什么，它是一种匹配模式， 不仅能匹配匹配字符，还能匹配位置 ，不少人忽略了匹配字符这个作用，往往碰到这种问题就手足无措。 如果正则只有精确匹配是没有多大意义的，比如： 正则表达式的强大之处在于它的模糊匹配，分为横向模糊和纵向模糊 横向模糊：一个正则可匹配的字符串的长度不是固定的，可以是多种情况的 其实现的方式是使用量词： 比如： 横向模糊匹配到了多种情况，案例中用的正则是/ab{2,5}c/g，后面多了g，它是正则的一个修饰符。

表示全局匹配，即在目标字符串中按顺序找到满足匹配模式的所有子串，强调的是“所有”，而不只是“第一个”。

纵向模糊：一个正则匹配的字符串，具体到某一位字符时，它可以不是某个确定的字符，可以有多种可能 其实现的方式是使用范围类 -表示连字符，在此处作特殊用处，但是如果我要匹配'a-z'这三个字符呢？可以这么写： 这样引擎就不会认为它们是一个氛围了， 符号在范围类中起取反的作用， a表示除了a的所有字符。 系统根据范围类又预定义了一些类方便我们使用： 不加g就是惰性匹配，我匹配完一个就不敢了，懒得再干其他事儿了，加了g就是贪婪模式了,我现在精力无限，会尽可能的干事儿，但是我还有些理智，不会干超出能力之外的事儿，比如你给我的范围是{2,5}，我会尽可能做5件事儿，但是不会超过5件事,反正只要在能力范围内，越多越好 此时我既想尽可能的匹配又想让它不那么贪婪有没有办法呢？办法是有的, 贪婪模式一般作用在量词这里，限制在量词这里就好了 ，可以在量词这里加一个？即可搞定。 其中/\d{2,5}?/表示，虽然2到5次都行，当2个就够的时候，就不在往下尝试了。 此时就达到了我们的要求,不过这里完全是为了讲解贪婪模式和惰性模式，并不推荐这么做，我完全可以将{2,5}改成{2}，一样的效果 知道了惰性模式的原理，我们完全可以鼓捣出其他的各式各样的情形： 一个模式可以实现横向和纵向模糊匹配。

而多选分支可以支持多个子模式任选其一 具体形式如下：(p1|p2|p3)，其中p1、p2和p3是子模式，用“|”（管道符）分隔，表示其中任何之一 但有个事实我们应该注意，比如我用/good|goodbye/，去匹配"goodbye"字符串时，结果是"good" 而把正则改成/goodbye|good/，结果是 也就是说，分支结构也是惰性的，即当前面的分支匹配上了，后面的就不再尝试了 并且，使用分支的时候注意使用括号， 匹配字符，无非就是范围类、量词和分支结构的组合使用罢了 分析： 表示一个16进制字符，可以用范围类[0-9a-fA-F] 其中字符可以出现3或6次，需要是用量词和分支结构 使用分支结构时，需要注意顺序(惰性) 分析： 对每个地方的数字进行分析： 共4位数字，第一位数字可以为[0-2]。 当第1位为2时，第2位可以为[0-3]，其他情况时，第2位为[0-9]。 第3位数字为[0-5]，第4位为[0-9] 如果也要求匹配7:9，也就是说时分前面的0可以省略: 分析： 年，四位数字即可，可用[0-9]{4}。

月，共12个月，分两种情况01、02、……、09和10、11、12，可用(0[1-9]|1[0-2])。 日，最大31天，可用(0[1-9]|[12][0-9]|3[01]) 分析： 整体模式是: 盘符:\文件夹\文件夹\文件夹 其中匹配F:\，需要使用[a-zA-Z]:\，其中盘符不区分大小写，注意\字符需要转义。 文件名或者文件夹名，不能包含一些特殊字符，此时我们需要排除范围类[ \:*<>|"?\r\n/]来表示合法字符。

另外不能为空名，至少有一个字符，也就是要使用量词+。因此匹配“文件夹\”，可用[ \:*<>|"?\r\n/]+\。 另外“文件夹\”，可以出现任意次。

也就是([^\: <>|"?\r\n/]+\) 。其中括号提供子表达式。 路径的最后一部分可以是“文件夹”，没有\，因此需要添加([^\:*<>|"?\r\n/]+)?。 最后拼接成了一个看起来比较复杂的正则： 用到了惰性匹配，防止把class也提取出来 优化： ^（脱字符）匹配开头，在多行匹配中匹配行开头。

$（美元符号）匹配结尾，在多行匹配中匹配行结尾 比如我们把字符串的开头和结尾用"#"替换（位置可以替换成字符的！）： 多行匹配模式时，二者是行的概念，这个需要我们的注意 \b是单词边界，具体就是\w和\W之间的位置，也包括\w和^之间的位置，也包括\w和$之间的位置 首先，我们知道，\w是范围类[0-9a-zA-Z_]的简写形式，即\w是字母数字或者下划线的中任何一个字符。而\W是排除范围类[^0-9a-zA-Z_]的简写形式，即\W是\w以外的任何一个字符 此时我们可以看看"[#JS#] #Lesson_01#.#mp4#"中的每一个"#"，是怎么来的。 第一个"#"，两边是"["与"J"，是\W和\w之间的位置。 第二个"#"，两边是"S"与"]"，也就是\w和\W之间的位置。

第三个"#"，两边是空格与"L"，也就是\W和\w之间的位置。 第四个"#"，两边是"1"与"."，也就是\w和\W之间的位置。 第五个"#"，两边是"."与"m"，也就是\W和\w之间的位置。 第六个"#"，其对应的位置是结尾，但其前面的字符"4"是\w，即\w和$之间的位置。

知道了\b的概念后，那么\B也就相对好理解了。 \B就是\b的反面的意思，非单词边界。例如在字符串中所有位置中，扣掉\b，剩下的都是\B的。

具体说来就是\w与\w、\W与\W、^与\W，\W与$之间的位置 exp1(?=exp2) 表达式会匹配exp1表达式，但只有其后面内容是exp2的时候才会匹配 exp1(?=exp2) 表达式会匹配exp1表达式，但只有其后面内容不是exp2的时候才会匹配 (?=p)，其中p是一个子模式，即p前面的位置 比如(?=l)，表示'l'字符前面的位置，例如： 而(?!p)就是(?=p)的反面意思 对于位置的理解，我们可以理解成空字符"" 因此，把/ hello$/写成/ ^hello$$$/，是没有任何问题的： 也就是说字符之间的位置，可以写成多个。 把位置理解空字符，是对位置非常有效的理解方式 此正则要求只有一个字符，但该字符后面是开头。 比如把"12345678"，变成"12,345,678"。

可见是需要把相应的位置替换成"," 使用(?=\d{3}$)就可以做到： 因为逗号出现的位置，要求后面3个数字一组，也就是\d{3}至少出现一次。 此时可以使用量词+： 此时会出现问题： 上面的正则，仅仅表示把从结尾向前数，一但是3的倍数，就把其前面的位置替换成逗号 怎么解决呢？我们要求匹配的到这个位置不能是开头。 我们知道匹配开头可以使用^，但要求这个位置不是开头怎么办？ easy，(?!^) 如果要把"12345678 123456789"替换成"12,345,678 123,456,789"。 此时我们需要修改正则，把里面的开头^和结尾$，替换成\b 其中(?!\b)怎么理解呢？ 要求当前是一个位置，但不是\b前面的位置，其实(?!\b)说的就是\B。

因此最终正则变成了：/\B(?=(\d{3})+\b)/g 此题，如果写成多个正则来判断，比较容易。但要写成一个正则就比较困难。 那么，我们就来挑战一下。

看看我们对位置的理解是否深刻 我们可以把原题变成下列几种情况之一： 1.同时包含数字和小写字母 2.同时包含数字和大写字母 3.同时包含小写字母和大写字母 4.同时包含数字、小写字母和大写字母 上面的正则看起来比较复杂，只要理解了第二步，其余就全部理解了。 /(?=.*[0-9])^[0-9A-Za-z]{6,12}$/ 对于这个正则，我们只需要弄明白(?=.*[0-9])^即可。 分开来看就是(?=.*[0-9])和^。 表示开头前面还有个位置（当然也是开头，即同一个位置，想想之前的空字符类比）。

(?=. [0-9])表示该位置后面的字符匹配. [0-9]，即，有任何多个任意字符，后面再跟个数字。 另一种解法： “至少包含两种字符”的意思就是说，不能全部都是数字，也不能全部都是小写字母，也不能全部都是大写字母。 那么要求“不能全部都是数字”，怎么做呢？(?!p)出马！ 三种'都不能'呢？ 1.分组和分支结构 括号是提供分组功能，使量词'+'作用于z和这个整体 而在多选分支结构(p1|p2)中，此处括号的作用也是不言而喻的，提供了子表达式的所有可能 而要使用它带来的好处，必须配合使用实现环境的API 以日期为例。

假设格式是yyyy-mm-dd的 提取数据： match返回的一个数组，第一个元素是整体匹配结果，然后是各个分组（括号里）匹配的内容，然后是匹配下标，最后是输入的文本 可以使用正则对象的exec方法： 也可以使用构造函数的全局属性$1至$9来获取： 替换: 想把yyyy-mm-dd格式，替换成mm/dd/yyyy怎么做？ 反向引用: 比如要写一个正则支持匹配如下三种格式： 注意里面的\1，表示的引用之前的那个分组(-|/|.)。不管它匹配到什么（比如-），\1都匹配那个同样的具体某个字符 括号嵌套怎么办？ 以左括号（开括号）为准 \10是表示第10个分组，还是\1和0呢？答案是前者，虽然一个正则里出现\10比较罕见 引用不存在的分组会怎样？ 因为反向引用，是引用前面的分组，但我们在正则里引用了不存在的分组时，此时正则不会报错，只是匹配反向引用的字符本身。例如\2，就匹配"\2"。注意"\2"表示对2进行了转意 。

将正则表达式(aa|b)*a(a|bb)转化成dfa

此正则表达式化简后为a*b*即空字符串，或者仅由a组成的字符串，或者仅有b组成的字符串，或者由若干a后面接若干b组成的字符串。 (A|B)*表示A或者B出现若干次或者不出现。

(A*B*)* A出现若干次或者不出现，B出现若干次或者不出现，一起出现若干次或者不出现 (A*|B*)* A出现若干次或者不出现或者B出现若干次或者不出现，一起出现若干次或者不出现。

任何一个字符串都匹配这个字符串。 简介 正则表达式是对字符串和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。

正则表达式概述 什么是正则表达式

正则表达式概述 正则表达式在程序设计语言中存在着广泛的应用，特别是用来处理字符串。如匹配字符串、查找字符串、替换字符串等。

可以说，正则表达式是一段文本或一个公式，它是用来描述用某种模式去匹配一类字符串的公式，并且该公式具有一定的模式。

本小节将介绍正则表达式的基本概念、第一个正则表达式，以及测试正则表达式的工具Code Architects Regex Tester。 什么是正则表达式 正则表达式（Regular Expression）起源于人类神经系统的早期研究。神经生理学家Warren McCulloch和Walter Pitts研究出一种使用数学方式描述神经网络的方法。1956年，数学家Stephen Kleene发表了一篇标题为“神经网事件的表示法”的论文，并在该论文中引入了“正则表达式”这一个概念。

该论文称正则表达式是：“正则集的代数”的表达式。因此，采用“正则表达式”这个术语。正则表达式的定义存在多种说法，具体如下： 正则表达式就是用某种模式去匹配一类字符串的公式，主要用来描述字符串匹配的工具。

正则表达式描述了一种字符串匹配的模式。它可以用来检查字符串是否含有某种子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。 正则表达式是由普通字符（如字符a到z）以及特殊字符（称为元字符）组成的文字模式。

正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。 正则表达式就是用于描述某些规则的工具。这些规则经常用于处理字符串中的查找或替换字符串。

换句话说，正则表达式就是记录文本规则的代码。 正则表达式就是用一个“字符串”来描述一个特征，然后去验证另一个“字符串”是否符合这个特征。 学过《编译原理》的读者可能知道不确定有限自动机（Non-deterministic finite automaton，简称NFA）和确定有限自动机（Deterministic finite automaton，简称DFA）。其实，正则表达式是一个不确定有限自动机。

NFA和DFA的最大区别在于它们的状态转换函数。NFA可以对同一个字符串产生多种理解方式，而DFA则只有唯一的一种理解方式。也正因为如此，NFA在匹配过程中可能会回溯，NFA的效率一般要低于DFA。因此，在书写正则表达式时尽量减少回溯来提高正则表达式的效率。

如果你使用过Windows或DOS下用于文件查找的通配符*和?，那么你不难理解正则表达式。如果你需要查找所有Word文档，那么可能使用表达式*.doc。其中，字符*是一个通配符，它可以代表任意字符串。正则表达式和通配符具有相似性，它也可以使用一些字符（如字符.）表示任意字符。

然而，它比通配符更具有精确性。 在正则表达式中，匹配是最常用的一个词语，它描述了正则表达式动作结果。给定一段文本或字符串，使用正则表达式从文本或字符串中查找出符合正则表达式的字符串。

有可能文本或字符存在不止一个部分满足给定的正则表达式，这时每一个这样的部分被称为一个匹配。其中，匹配存在下面3种类型： 形容词性的匹配，即一个字符串匹配一个正则表达式。 动词性的匹配，即在文本或字符串里匹配正则表达式。

名词性的匹配，即字符串中满足给定的正则表达式的一部分。 正则表达式的应用非常广泛，特别是在字符串处理方面。目前来说，正则表达式已经在很多软件中得到广泛了应用，如Linux、Unix、HP等操作系统，C#、PHP、Java等程序开发环境，以及很多的应用软件中，都可以看到正则表达式的这样或那样的应用。正则表达式常见的应用如下： 验证字符串，即验证给定的字符串或子字符串是否符合指定特征，譬如验证是否是合法的邮件地址、验证是否为合法的HTTP地址等。

查找字符串，从给定的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。 替换字符串，即把给定的字符串中的符合指定特征的子字符串替换为其他字符串，比普通的替换更强大。 提取字符串，即从给定的字符串中提取符合指定特征的子字符串。