形式语言课件7

2013-7-17 24
7.1 基本定义
δ4(q1，0，A)={(q1，AA)} δ4(q1，1，A)={(q1，BA)} δ4(q1，0，B)={(q1，AB)} δ4(q1，1，B)={(q1，BB)} δ4(q1，2，A)={(q2，A)} δ4(q1，2，B)={(q2，B)} δ4(q2，0，A)={(q2，ε)} δ4(q2，1，B)={(q2，ε)}
此时有：N(M3)=L(M3)=L。
2013-7-17
23
7.1 基本定义
• 不追求让PDA同时用终止状态和空栈接受 同样的语言，还可以删除状态qf。这样我们 可以得到PDA M4 。 • M4=({q0，q1，q2 }，{0，1，2}，{ A，B， Z0}，δ4，q0，Z0，Φ) δ4(q0，0，Z0)={(q1，AZ0)} δ4(q0，1，Z0)={(q1，BZ0)} δ4(q0，2，Z0)={(q2，ε)}
2013-7-17
9
7.1 基本定义
• 符号使用约定 • 英文字母表较为前面的小写字母，如a，b ，c，„，表示输入符号； • 英文字母表较为后面的小写字母，如x，y ，z，„，表示由输入字符串； • 英文字母表的大写字母，表示栈符号； • 希腊字母α，β，γ，„，表示栈符号串
2013-7-17 10
2013-7-17 12
7.1 基本定义
• ├Mn是├M 的n次幂
– (q1，w1，β1)├Mn(qn，wn，βn)
• ├M*是├M 的克林闭包
– (q，w，α)├M*(p，x，β)
• ├M+是├M 的正闭包
– (q，w，α)├M+(p，x，β)
2013-7-17 13
7.1 基本定义
• M接受的语言 – M用终态接受的语言 • L(M)={w | (q0，w，Z0)├*(p，ε， β)且 p∈F} – M用空栈接受的语言 • N(M) ={w | (q0，w，Z0)├*(p，ε， ε)}
2013-7-17
31
7.2.1 PDA用空栈接受和用终止状 态接受等价
(q01，x，Z01Z02)├M2*(q，ε，γZ02)├M2*(qe， ε，ε)且q∈F (q01，x，Z01 Z02)├M2*(qe，ε，ε) (q02，x，Z02)├M2(q01，x，Z01Z02)├M2*(qe， ε，ε) (q02，x，Z02)├M2*(qe，ε，ε) x∈N(M2)
2013-7-17
14
7.1 基本定义
• 例 7-1 考虑接受语言L={w2wT | w∈{0,1}*} 的PDA的设计。 • 解法1： • 先设计产生L的CFG G1： G1：S2|0S0|1S1 • 再将此文法转化成GNF： G2：S2|0SA|1SB A0 B1
2013-7-17 15
2013-7-17 20
7.1 基本定义
• M3=({q0，q1，q2，qf，qt}，{0，1，2}，{ A，B， Z0}，δ3，q0，Z0，{qf})
• q0为开始状态 • q1为记录状态 • q2为匹配状态 • qf为终止状态 • qt陷阱状态
2013-7-17 21
7.1 基本定义
δ3(q0，0，Z0)={(q1，AZ0)} δ3(q0，1，Z0)={(q1，BZ0)} δ3(q0，2，Z0)={(qf，ε)} δ3(q1，0，A)={(q1，AA)} δ3(q1，1，A)={(q1，BA)} δ3(q1，0，B)={(q1，AB)} δ3(q1，1，B)={(q1，BB)}
定理 7-1 对于任意PDA M1，存在PDA M2，使 得N (M2)= L (M1)。 证明要点： （1） 构造。 设PDA M1 = (Q，∑，Γ，δ1，q01，Z01，F) 取PDA M2 = (Q∪{q02，qe}，∑，Γ∪{Z02}， δ，q02，Z02，F) 其中Q∩{q02，qe}=Γ∩{Z02}=Φ。
7.1 基本定义
• 即时描述(ID) (q，w，γ)∈(Q，∑*，Γ*)称为M的一 个即时描述。它表示M处于状态q，w是当 前还未处理的输入字符串，而且M正注视 着w的首字符，栈中的符号串为γ，γ的 最左符号为栈顶符号，最右符号为栈底 的符号，较左的符号在栈的较上面，较 右的符号在栈的较下面。
2013-7-17 11
7.1 基本定义
句子0102010的最左派生和我们希望相应的PDA M的动作 派生 S0SA 01SBA M应该完成的动作 从q0启动，读入0，将S弹出栈， 将SA压入栈，状态不变 在状态q0，读入1，将S弹出栈， 将SB压入栈，状态不变 在状态q0，读入0，将S弹出栈， 将SA压入栈，状态不变
2013-7-17 18
7.1 基本定义
M2=({q0,q1},{0,1,2},{S,A,B,Z0},δ2,q0,Z0,{q1}) δ2(q0，0，Z0)={(q0，SAZ0)} δ2(q0，1，Z0)={(q0，SBZ0)} δ2(q0，2，Z0)={(q1，ε)} δ2(q0，0，S)={(q0，SA)} δ2(q0，1，S)={(q0，SB)} δ2(q0，2，S)={(q0，ε)} δ2(q0，0，A)={(q0，ε)} δ2(q0，1，B)={(q0，ε)} δ2(q0，ε，Z0)={(q1，ε)} 此时有：N(M2)=L(M2)=L。
• PDA的物理模型
2013-7-17
3
7.1 基本定义
• PDA应该含有三个基本结构
– 存放输入符号串的输入带。 – 存放文法符号的栈。 – 有穷状态控制器。
• PDA的动作
– 在有穷状态控制器的控制下根据它的当前状 态、栈顶符号、以及输入符号作出相应的动 作，在有的时候，不需要考虑输入符号。
2013-7-17 4
7.1 基本定义
• 确定的PDA (q，a，Z)∈Q×∑×Γ， |δ(q，a，Z)|+|δ(q，ε，Z)|≤1 • PDA在每一个状态q和一个栈顶符号下的动 作都是惟一的。 • 关键
– 对于(q，Z)∈Q×Γ，M此时如果有非空移动 ，就不能有空移动。 – 每一种情况下的移动都是惟一的。
2013-7-17 27
2013-7-17 30
7.2.1 PDA用空栈接受和用终止状 态接受等价
（2） 证明N (M2)= L (M1)。 x∈L(M1) (q01，x，Z01)├M1*(q，ε，γ)且q∈F (q01，x，Z01Z02)├M1*(q，ε，γZ02)且q∈F (q01，x，Z01Z02)├M2*(q，ε，γZ02)且q∈F
7.2 PDA与CFG等价
• 对于任意PDA M1，存在PDA M2，使得 L(M2)=N(M1)； • 对于任意PDA M1，存在PDA M2，使得N (M2)= L (M1)。 • CFL可以用空栈接受语言的PDA接受。 • PDA接受语言可以用CFG描述。
2013-7-17
28
7.2.1 PDA用空栈接受和用终止状 态接受等价
010SABA
2013-7-17
16
7.1 基本定义
句子0102010的最左派生和我们希望相应的PDA M的动作 派生 0102ABA 01020BA M应该完成的动作 在状态q0，读入2，将S弹出栈， 将ε压入栈，状态不变 在状态q0，读入0，将A弹出栈， 将ε压入栈，状态不变 在状态q0，读入1，将B弹出栈， 将ε压入栈，状态不变 在状态q0，读入0，将A弹出栈， 将ε压入栈，状态 基本定义
• δ——状态转移函数，有时候又叫做状态 转换函数或者移动函数。
δ：Q×(∑∪{ε})×Γ
2
Q *
2013-7-17
7
7.1 基本定义
δ(q，a，Z)={(p1，γ1)，(p2，γ2)，„， (pm，γm)} • 表示M在状态q，栈顶符号为Z时，读入字符 a，对于i=1，2，„，m，可以选择地将状 态变成pi，并将栈顶符号Z弹出，将γi中的 符号从右到左依次压入栈，然后将读头向 右移动一个带方格而指向输入字符串的下 一个字符。
2013-7-17 29
7.2.1 PDA用空栈接受和用终止状 态接受等价
δ2(q02，ε，Z02)={(q01，Z01Z02)} (q,a,Z)∈Q×∑×Γ, δ2(q,a,Z)=δ1(q,a,Z)； (q,Z)∈(Q-F)×Γ, δ2(q,ε,Z)=δ1(q,ε,Z)； (q,Z)∈F×Γ δ2(q,ε,Z)=δ1(q,ε,Z)∪{(qe,ε)}； q∈F,δ2(q,ε,Z02)= {(qe,ε)}； Z∈Γ∪{Z02},δ2(qe,ε,Z)= {(qe,ε)}
2013-7-17 22
7.1 基本定义
δ3(q1，2，A)={(q2，A)}
δ3(q1，2，B)={(q2，B)}
δ3(q2，0，A)={(q2，ε)}
δ3(q2，0，B)={(qt，ε)}
δ3(q2，1，B)={(q2，ε)}
δ3(q2，1，A)={(qt，ε)}
δ3(q2，ε，Z0)={(qf，ε)}
7.1 基本定义
如果(p，γ)∈δ(q，a，Z)，a∈∑，则 (q，aw，Zβ)├M(p，w，γβ) 表示M做一次非空移动，从ID(q，aw，Zβ)变 成ID(p，w，γβ)。 如果(p，γ)∈δ(q，ε，Z)，则 (q，w，Zβ)├M(p，w，γβ) 表示M做一次空移动，从ID(q，aw，Zβ)变成 ID(p，w，γβ) 。
7.1 基本定义
• 下推自动机(PDA) M= (Q，∑，Γ，δ，q0，Z0，F) Q——状态的非空有穷集合。q∈Q，q 称为M的一个状态 ∑——输入字母表。要求M的输入字符串 都是∑上的字符串； Γ——栈符号表。 A∈Γ，叫做一个栈符号；
2013-7-17 5
7.1 基本定义
• Z0——Z0∈Γ叫做开始符号，是M启动时候 栈内惟一的一个符号。所以，习惯地称其 为栈底符号； • q0——q0∈Q，是M的开始状态，也可叫做初 始状态或者启动状态； • F——FQ，是M的终止状态集合，简称为终 态集。q∈F，q称为M的终止状态，也可称 为接受状态，简称为终态。