2-张延亮—正规式和有穷自动机的等价性

7
2.4 写出下述语言的正规式描述 （4）C的形如/*…*/ 的注释。其中…代表不含*/的字符串 思路：接收*/的DFA->不接收*/的DFA->RE 接收*/的DFA中有3个状态：没有接收*；接收了*；接收了*/
x
([^*] | **[^*/])* ** /* ([^*] | **[^*/])* ** */
10
2.10
该DFA从初态到终态有三条路径：b|c|a(a|c)*b，而且是 这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)*b)+
11
3.6 设字母表∑={0,1}，设计下列语言的文法。对于正规语言 ，可用正规式表示。 （2）0和1个数相等的字符串； （3）0和1个数不相等的字符串； （2）（3）均不能用正规式表示，为什么？（鸽巢原理反证） （2）思路：S包含0、1个数相等，0、1相等的最小项是ε、01 、10，则给它们加上S，则0、1个数仍相等 S -> S0S1S | S1S0S | ε 消除直接左递归 S -> S’ S’ -> 0S1SS’ | 1S0SS’ | ε 即是S -> 0S1S | 1S0S | ε 这些文法都等价
end;
两种解题的思路： 1. 把自己当作计算机，按照参数传递的实现方式“运行”一 遍程序，得出结果； 2. 找台机子把程序敲进去试试（辅助手段） 表达式a+b如何可以作为复写-恢复的实参？ 解决方案：忽略返回值问题（因为复写-恢复一般要求形参要 有左值） 考试中不会有这样很困惑的问题！
17
5.5 有一过程A如下所示。采用静态作用域、最近嵌套原则， 设A是第0层的过程。
15
3.19 假设所讨论的文法是非二义的，说明为什么在规范归约 中，非终结符绝不会出现在句柄的右边。 解：（解题思路：用反证的方法，假设在规范归约中句柄右边 有非终结符，则推出矛盾） 假设在规范归约中有句型“...α...A...”，其中α是句柄， A非终结符。 根据规范归约定义，A必定是由句型中相对于A的短语归约 而来。而A的短语在α右边（即先归约了右边的短语），与规 范归约矛盾。 得证。 请进一步思考：为什么假设文法是非二义的？

对每一个NFA M 都存在 都存在DFA M ′使得 定理 对每一个 L(M)=L(M ′)
用M′=〈Q′,Σ,δ′,q0′,F′ 〉 模拟 M=〈Q,Σ,δ,q0,F 〉 ′ 〈 ′ ′ ′ 〈 Q′=P(Q), q0′={q0} ′ F′={ A∈Q | A∩F≠∅} ′ ∈ ∅ ∀A∈Q 和 a∈Σ, ∈ ∈
7
例2 (续) 续
δ*(q0 ,w) w 1 {q0, q1} 10 {q0, q3} 101 {q0, q1} 1011 {q0, q1 , q2} 10110 {q0, q2 , q3} L(G) = { x00y, x11y | x,y∈{0,1}*} ∈
8
DFA与NFA的等价性 与 的等价性
∗ n
L(M)={a2k+1 | k∈N} ∈
4
非确定型有穷自动机
定义 非确定型有穷自动机 (NFA) M =〈 Q,Σ,δ,q0,F 〉, 〈 其中 Q,Σ, q0, F 的定义与 DFA 的相同 而 的相同, δ: Q ×Σ→P(Q)
5
实例
一台NFA 例2 一台 δ 0 1 →q0 {q0 , q3} {q0 , q1} q1 ∅ {q2} *q2 {q2} {q2} q3 {q4} ∅ *q4 {q4} {q4}
21
11.2 有穷自动机
确定型有穷自动机(DFA) 确定型有穷自动机 非确定型有穷自动机(NFA) 非确定型有穷自动机 转移的NFA(ε-NFA) 带ε转移的 转移的
1
确定型有穷自动机
确定型有穷自动机(DFA)是一个有序 元组 是一个有序5元组 定义 确定型有穷自动机 是一个有序 M = 〈Q,Σ,δ,q0,F 〉, 其中 状态集合Q: (1) 状态集合 非空有穷集合 (2) 输入字母表 非空有穷集合 输入字母表Σ: (3) 状态转移函数 状态转移函数δ:Q×Σ→Q × 控制器 (4) 初始状态 q0∈Q (5) 终结状态集 F⊆Q ⊆

2018年11月24日星期六
南京航空航天大学计算机学院 胡军
16
1.3 非确定的有穷自动机(NFA)
一个FA(字母表为{0,1}),接受所有结尾是101的字符串。
能否给FA增加猜测选择的能力？假设我们具有猜测何时输入串还 剩下三个字符的能力。
还剩三个字符 1 0 1 qdie
2018年11月24日星期六 南京航空航天大学计算机学院 胡军 17
NFA：可以进行猜测选择
0, 1 q0 1 q1 0 q2 1 q3
q3 没有任何转换出来； q3 上如果读入0,1, NFA也运行进入死状态。
2018年11月24日星期六
南京航空航天大学计算机学院 胡军
21
NFA： 猜测的能力
猜测是否已经到了最后三位字符的 位置了？
0, 1
q0
1
q1
0
2018年11月24日星期六
南京航空航天大学计算机学院 胡军
25
NFA与 DFA的等价
NFA 能识别（接受）DFA所识别（接受）的所有语 言。（为什么？） 反过来成立吗？
YES
任一个NFA都能转换成一个DFA，二者所 识别的语言是相等的。
2018年11月24日星期六 南京航空航天大学计算机学院 胡军 26
提示：DFA得记住 读入字符串的最后两位。
qe
q0 0
1
0 1
DFA 例子
设计一个DFA(字母表为{0,1}),接受所有结尾 是101的字符串。
2018年11月24日星期六
南京航空航天大学计算机学院 胡军
10
DFA 例子
例3.1 给出一个有穷自动机 Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0}) 其中：转移函数δ具体定义如下：

其编译过程采用一趟扫描方式 以语法、语义分析程序为核心 词法分析程序和代码生成程序都作为一个过程，当语法分 析需要读单词时就调用词法分析程序，而当语法、语义 分析正确，需要生成相应的目标代码时，则调用代码生 成程序。 表格管理程序实现变量，常量和过程标识符的信息的登 录与查找。 出错处理程序，对词法和语法、语义分析遇到的错误给 出在源程序中出错的位置和与错误 性质有关的编号，并 进行错误恢复。
ε 1 ε
SFA(A)
ε
SFA(B) ε
ε SFA(B)
SFA(A)
1 正则表达式到有穷自动机

结构化自动机
– RE = A*
ε 1 ε SFA(A) ε ε
1 正则表达式到有穷自动机

结构化自动机举例
– – – – – – – a a| b ab a* a(b|c) (a|b)(a|c) (a|b)c*
1 正则表达式到有穷自动机

正则表达式到有穷自动机的转换
– 正则表达式到NFA – NFA到DFA转换 – DFA极小化 – DFA等价性
1 正则表达式到有穷自动机

结构化自动机
– RE = ε –RE = a
1
ε
2
1
a
2
1 正则表达式到有穷自动机

结构化自动机
– RE = A | B – RE = AB
词法分析过程GETSYM所要完成的任务： –读源程序（getch) –滤空格 –识别保留字 –识别标识符 –拼数 –识别单字符单词 –拼双字符单词
实验报告格式

格式
– – – – 实验目的 主要软件 分析过程（算法、重点语句、对应书中的原理） 实验的结论、建议与设想