正则表达式

「正则表达式」（RE）是一种用来描述「正则语言」的「更紧凑」的表示方法。

正则表达式的定义

上面的优先级的顺序是「从高到低」

例子

正则语言

可以用正则表达式定义的语言叫做「正则语言或正则集合」

正则文法与正则表达式等价

对任意正则文法「G」，存在定义同一语言的正则表达式「r」。对任何正则表达式r，存在生成同一语言的正则文法G

正则定义

例子

有穷自动机(FA)

例子

最长字串匹配原则

上面的意思是：假设输入的是<=，那么自动机识别到<之后到达终态，会继续查看下一个符号，尽可能找到最长的匹配。那么对于<=来说，就匹配到「2」这个终态。

有穷自动机的分类

❝

又穷自动机分成两类：确定的FA——DFA，非确定的FA——NFA

❞

DFA例子

「非确定的有穷自动机（NFA）」是从状态S出发，沿着标记位a的边「不止一个路径」

NFA例子

等价性

上面可以看出：正则文法与正则表达式等价，正则表达式与自动机等价 还是NFA比较好识别。但是从计算机的角度来说，DFA比较好实现

带有“生成ε边”的NFA

从上面可以看出，A状态可以在不接收任何字符的情况下进入B状态，但进入B状态之后就不能再接收0号信号。

从正则表达式到有穷自动机

正则表达式（RE）直接到DFA是不太好实现的，所以我们通过NFA

根据RE(正则表达式)构造NFA

例子

❝

1. 先画起始状态和终止状态
2. 把正则表达式分成多个子表达式
3. 然后对各个子表达式进行转换工作

❞

从NFA到DFA的转换

模仿上面怎么写的就可以。