按正则文法确定有限态自动机举例

【编译原理】词法分析：正则表达式与有限⾃动机基础引⾔： 编译语⾔设计的精髓在于⾃动化过程，即如果要设计⼀门编程语⾔，那么⼀定要设计⼀个⾃动化系统，能够⾃⾏读⼊分析程序员写⼊的程序，将其翻译为机器能够识别的指令等信息。

当然⾼级语⾔的编译不是⼀蹴⽽就的，⽽是通过若⼲步的分解、规约、转换、优化，最后得到⽬标程序。

具体的编译步骤如下： 源程序就是我们写⼊的⾼级语⾔，编译的第⼀步叫做“词法分析”。

词法分析的本质，就是要拆解出语句的每⼀个单词，然后对这个单词的类型进⾏辨识。

⾸先拿中⽂来举例。

⽐如有⼀句话是“我喜欢你”，那么⾸先我们要把这句话拆成“我”、“喜欢”、“你”，然后再逐个分析他们的类型，得到“我”->主语；“喜欢”->谓语；“你”->宾语。

这样我们就把这句话每个单词都分析出来了，也就完成了中⽂的“词法分析”。

那么回到编程语⾔，它的词法分析就是将字符序列转换为单词（Token）序列的过程。

翻译成俗话，就是把我们写的⼤⽚语⾔⽂本分解为⼀个⼀个单词，再输出每个单词的类型。

举⼀个例⼦：int p = 3 + a; 这个语句⾮常简单，即定义⼀个变量p，它的初值为变量a与3的加和。

那么接下来我们要对这个语句进⾏词法分析，⾸先我们要把这段⽂本拆解成单词，拆出来就是'int'、'p'、'='、'3'、'+'、'a'、';'。

对这些单词再进⾏类型的辨识，那么就得到以下结果：语素语⾔类型int关键字p标识符=运算符3数字+运算符a标识符 这样我们就把这段⽂本中的每个单词的类型都分析出来了。

乍⼀看⾮常简单对不对，对于⼈类⽽⾔你只需要⽤⾁眼就可以轻松观察出来每个单词的类型，但对于计算机⽽⾔，它可没有⼈类那样的智能。

如果想要计算机能够识别并分析语素的类型，那就需要我们⼈类来为它构造⼀个⾃动化输⼊和分析的系统。

确定有限状态⾃动机⽬录思路确定有限状态⾃动机确定有限状态⾃动机（以下简称「⾃动机」）是⼀类计算模型。

它包含⼀系列状态，这些状态中：有⼀个特殊的状态，被称作「初始状态」。

还有⼀系列状态被称为「接受状态」，它们组成了⼀个特殊的集合。

其中，⼀个状态可能既是「初始状态」，也是「接受状态」。

起初，这个⾃动机处于「初始状态」。

随后，它顺序地读取字符串中的每⼀个字符，并转移到下⼀个状态。

当字符串全部读取完毕后，如果⾃动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。

本题使⽤有限状态⾃动机。

根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。

按照字符串从左到右的顺序，定义以下 9 种状态：0. 开始的空格1. 幂符号前的正负号2. ⼩数点前的数字3. ⼩数点、⼩数点后的数字4. 当⼩数点前为空格时，⼩数点、⼩数点后的数字5. 幂符号6. 幂符号后的正负号7. 幂符号后的数字8. 结尾的空格结束状态：合法的结束状态有 2, 3, 7, 8 。

代码class Solution {public boolean isNumber(String s) {Map[] states = {new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.new HashMap<>() {{ put('d', 2); put('.', 4); }}, // 1.new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.new HashMap<>() {{ put('d', 3); }}, // 4.new HashMap<>() {{ put('s', 6); put('d', 7); }}, // 5.new HashMap<>() {{ put('d', 7); }}, // 6.new HashMap<>() {{ put('d', 7); put(' ', 8); }}, // 7.new HashMap<>() {{ put(' ', 8); }} // 8.};int p = 0;char t;for(char c : s.toCharArray()) {if(c >= '0' && c <= '9') t = 'd';else if(c == '+' || c == '-') t = 's';else if(c == 'e' || c == 'E') t = 'e';else if(c == '.' || c == ' ') t = c;else t = '?';if(!states[p].containsKey(t)) return false;p = (int)states[p].get(t);}return p == 2 || p == 3 || p == 7 || p == 8;}}。

正规⽂法与正规式　3型⽂法也叫作正规⽂法，它对应于有限状态⾃动机，它是在2型⽂法的基础上满⾜：A->a|aB（右线性）或A->a|Ba（左线性）。

如果有A->a,A->aB,B->a,B->cB则符合3型⽂法的要求。

但是A->ab,A->aB,B->a,B->cB或A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。

也就是说，不能够推导出两个终结符，⽽且左线性和右线性只能使⽤⼀种，不能够同时出现。

1.分别写出描述以下语⾔的正规⽂法和正规式：（1）L1={ab n a|n≥0}。

（2）L2={a m b n|n≥1,m ≥1}（3）L3={（ab）n|n≥1}答：（1） S → aA A → bA | a L1 = ab*a （2）S → aAA → aA | bB | b B → bB | b L2 = a*b* （3）S → aA A → bB B → aA | ε L3 = (ab)*2.将以下正规⽂法转换到正规式·Z→0A· A→0A|0B· B→1A|ε答：Z = 0A A = 0A + 0B B = 1A + ε A = 0A + 0(1A + ε) = 0A + 01A + 0 A = aA | b Z = 0(0 | 01)*0Z→U0|V1 U→Z1|1 V→Z0|0答：Z = U0 + V1 U = Z1 + 1 V = Z0 + 0 Z = (Z1+1)0 + V1 Z = (Z1+1)0 +(Z0+0)1 Z = Z10 + 10 +Z01 + 01 Z = Z(10+01)+10+01 Z = (10+01)*1001 Z = (10 | 01)*1001S→aA A→bA|aB|b B→aA答：S = aAA = bA + aB + b B = aA A = bA + a(aA) +b = (b + aa)A +b S = (b | aa)*bI→l|Il|Id答： I = l + Il + Id I = l + I(l +d) I = l(l | d)*。

dfa经典案例以下是15个DFA（确定性有限自动机）经典案例：确定型有限自动机（DFA）：一个经典的例子是识别由0和1组成的字符串是否只包含一个数字。

比如，一个DFA可以识别输入的字符串是否只包含数字00-99之间的数字。

识别是否为一个有效的括号序列：使用DFA可以判断一个由“{”，“}”，“(”，“)”组成的字符串是否为有效的括号序列。

例如，输入的字符串为“()”或“(()”或“((()))”或“{()}”都是有效的，但“(({()))”或“(()){}”都是无效的。

识别单词是否为回文字符串：可以使用DFA来识别一个单词是否是回文的。

识别一个字符串是否是交替的“01”序列：DFA可以识别一个字符串是否由交替的0和1组成。

识别一个字符串是否是一个质数：DFA可以识别一个字符串是否表示一个质数。

识别一个字符串是否是一个阿姆斯特朗数：DFA可以识别一个字符串是否表示一个阿姆斯特朗数。

识别一个字符串是否是一个水仙花数：DFA可以识别一个字符串是否表示一个水仙花数。

识别一个字符串是否是一个卡布奇诺数：DFA可以识别一个字符串是否表示一个卡布奇诺数。

识别一个字符串是否是一个完全平方数：DFA可以识别一个字符串是否表示一个完全平方数。

确定一个字符串中的最长重复子串：DFA可以用来确定一个字符串中的最长重复子串的长度。

确定一个字符串中的最长回文子串：DFA可以用来确定一个字符串中的最长回文子串的长度。

确定一个字符串中的最长公共子串：DFA可以用来确定两个字符串之间的最长公共子串的长度。

确定一个字符串中的最长递增子串：DFA可以用来确定一个字符串中的最长递增子串的长度。

确定一个字符串中的最长递减子串：DFA可以用来确定一个字符串中的最长递减子串的长度。

词法分析器的设计：在编译原理中，词法分析器是一个将输入的字符流转化为记号流的有限自动机，记号是一些有意义的单词或符号。

例如，词法分析器可以识别输入的字符流中的关键字、标识符、运算符、常量等记号，并输出相应的记号流。

第2章程序语⾔基础知识（⽂法-正规式-有限⾃动机第2章程序语⾔基础知识编译原理2-781.⽂法认识终结符（不可拆分，⼩写）和⾮终结符（可拆分，⼤写）终结符不可单独置前eg:有⽂法G2[S]为：S->ApS->BqA->aA->cAB->bB->dB则：S为开始符，S,A,B为⾮终结符，p,q,a,b,c,d为终结符⽂法的类型0型⽂法（限制最少的⼀个）设G=（V N，V T ，P，S），如果它的每个产⽣式α---→β是这样结构：α属于（V N并V T）*（闭包）且⾄少含有⼀个⾮终结符，⽽β属于（V N并V T）*，则G是⼀个0型⽂法。

0型⽂法也称短语⽂法。

⼀个⾮常重要的理论结果是：0型⽂法的能⼒相当于图灵机（Turing）。

或者说，任何0型语⾔都是递归可枚举的，反之，递归可枚举集必定是⼀个0型语⾔。

1型⽂法也叫上下⽂有关⽂法，此⽂发对应于线性有界⾃动机。

它是在0型⽂法的基础上每⼀个α---→β,都有|β|>=|α|。

这⾥的|α|表⽰的是α的长度。

注意：虽然要求|β|>=|α|，但有⼀特例：α---->空也满⾜1型⽂法。

如有A->Ba 则|β|=2，|α|=1 符合1型⽂法要求。

反之，如aA->a,则不符合1型⽂法要求。

2型⽂法也叫上下⽂⽆关⽂法，它对应于下推⾃动机。

2型⽂法是在1型⽂法的基础上，再满⾜每⼀个α-→β都有α是⾮终结符。

如A->Ba,符合2型⽂法要求。

如Ab->Bab虽然符合1型⽂法要求，但是不符合2型⽂法要求，其中α=Ab,Ab 不是⼀个⾮终结符。

3型⽂法也叫正规⽂法，它对应于有限状态⾃动机。

它是在2型⽂法满⾜的基础上满⾜：A->α|αB（右线性）或A->α|Bα(左线性)如：A->a,A->aB,B->a,B->cB,则符合3型⽂法的要求。

但如果推导为：A->ab,A->aB,B->a,B->cB或：A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。