形式语言与自动机格雷巴赫范式转换

2)在输入<M2>上运行R。
3) 如果R接受，则接受；如果R拒绝，则拒绝。”
10
语言理论中的不可判定问题
定理 5.4 EQTM是不可判定的。
设TM R判定EQTM。如下构造判定ETM 的TM S：
S=“对于输入<M>，其中M是TM：
1)在输入<M，M1>上运行R，其中M1是拒绝所有输入的图 灵机。 2)如果R接受，则接受；如果R拒绝，则拒绝。 如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可 判定的，故EQTM也是不可判定的。
历史，M也就不接受w. 因此，S也就拒绝<M，w >。类似地，
如果R拒绝<B>，则B的语言不空。B能够接受的唯一串是M在 w 上的接受计算历史。这样，M必定接受w 。相应地，S也就 接受<M，w >。下图是检查这样一个TM计算历史的示意图。
B
…
#
x
q3 Ci
a
b
#
x
x Ci+1
q5
b
#
…
17
语言理论中的不可判定问题
题在算法上是不可解的。
25
一个简单的不可判定问题
在形式描述这个问题和给出它的证明之前，先来精确地描述这个
问题，然后表示成一个。骨牌簇P是pcp的一个实例：
P=
t1 b1
,
t2 b2
, … ,
tk bk
匹配是一个序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil. 问题是确定P是否有匹配。 令PCP={<G >| P是波斯特对应问题的一个实例，且P有匹配}
9
语言理论中的不可判定问题

f(qoe,0)= qee f(qoe,1)= qoo f(qeo,0)=qoo f(qeo,1)= qee
f（ qeo ,1）= qeeZ
所以串$1= 110101可以被M1接受。
f(qoo,0)=qeo f(qoo,1)= qoe
f（ qee , 110101 ）= f(f（ qee ,11010）,1)=
Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA)
一. NFA的定义
DFA的确定性表现在其映射函数是一个单值函 数。但是实际问题中，映射函数往往是一个多值函 数。
例如，源程序中扫描到一个字母时，不同的语言 对应多种情况：
FORTRAN中： 标识符/格式转换码E、D…
Ch2 形式语言自动机理论基础 2.2 自动机基础
第 2 章 形式语言与自动机基础
2.2 有限自动机基础 2.2.1 确定的有限状态自动机(DFA) 2.2.2 非确定的有限状态自动机(NFA) 2.2.3 NFA确定化 2.2.4 DFA化简
Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）
Q
q0
Z
其中状态转换函数f为：
f（q0，0）= {q0,q3}
f（q1，0）=
f（q2，0）= {q2} f（q3，0）= {q4} f（q4，0）= {q4}
f（q0，1）= {q0, q1} f（q1，1）={ q2} f（q2，1）= {q2}
f（q3，1）=
f（q4，1）={ q4}
Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA)
1) p0＝q0 2) f（pi，wi＋1）＝pi＋1，i＝0，1，，n－1 3) pnZ

16/93
ATM m REG
定义: 称AmB, 若有可计算函数f:**使得, w*, wA f(w)B.
设M是图灵机, w是串. RM,w=“对于输入x, 1) 若x=0n1n对某n>0, 则接受. 2) 在w上运行M. 若M接受w, 则接受x.”
• f3(<M,w>) = <RM,w> 是可计算函数. • L(RM,w) = * (正则) , 若M接受w; = {0n1n|n0}(非正则), 若M不接受w. • M,w, <M,w>ATM f3(<M,w>)REG.
19/93
LBA的格局总数
引理 对于LBA M, 若|Q|=q,||=g,输入串长为n, 则M的格局总数是qngn.
状态
…
w1
不同字符串数为gn, 读写头有n个不同位置, 共有q种不同状态.
w2
w3
…
wn
20/93
定理 ALBA是可判定的
ALBA={<M,w>|M是LBA,w是串,M接受w} 对比: ATM是不可判定的? 证明: T = “对于输入<M,w>,其中M是LBA,w是串, 1) 在w上模拟M qngn步, 或者直到M停机. 2) 若M停机,则当M接受时接受, 当M拒绝时拒绝; 若M还没有停机, 则拒绝.”
7/93
ATM到HALTTM的映射归约
• 对M,w, 构造映射g(<M,w>)=<FM,w>, 其中 FM = “对于输入x, 1) 在x上运行M. 2) 若M接受, 则接受;若M拒绝, 则一直左移.” • M,w, <M,w>ATM g(<M,w>)HALTTM. • 若HALTTM有判定器H, 则下面的S判定ATM. S = “对输入<M,w>, 1) 计算g(<M,w>). 2) 在g(<M,w>)上运行H. 3) 若H接受, 则接受; 若H拒绝, 则拒绝.”

等价性
定理7.1 如果对于某个按终结状态方式接受语言的PDA M1 ，有 L(M1)=L,则存在一个按空栈方式接受语言的PDA M2 ，使得N(M2)=L。
证明 设M1 =（Q，∑，Γ，δ，q0 ，Z0 ，F），构造 M2 =（Q∪{qe ，q0´}，∑，Γ∪{X0}，δ´，q0´ ，X0 ， δ´的第（2）条定义规定了M2按M1的动作去做，也就是对一切q∈Q，a∈∑∪{ε}
δ（q1 ，0，R）={（q1 ，BR）} 遇0，栈中加入B。 δ（q1 ，0，B）={（q1 ，BB）} δ（q1 ，1，R）={（q1 ，GR）} 遇1，栈中加入G。 δ（q1 ，1，G）={（q1 ，GG）} δ（q1 ，1，B）={（q1 ，GB）} δ（q1 ，0，G）={（q1 ，BG） 遇0，栈中加入B。 δ（q1 ，c，B）={（q2 ，B）} 遇对称中心c，改变状态，栈不动。 δ（q1 ，c，G）={（q2 ，G）} δ（q2 ，0，B）={（q2 ，ε）} 遇对称符号，消栈顶。 δ（q2 ，1，G）={（q2 ，ε）} δ（q2 ，ε，R）={（q2 ，ε）} 当再遇栈底R时，表示已读过的串符合要求，将栈变 空，表示接受。 δ（q1 ，ε，R）={（q2 ，ε）} 处理当w=ε时的特殊情况，即输入串只有c，也 被接受。
对于例7.1中的PDA M，用扩充转移图表示就是：
图中从q0到q1的有向边上标记为0,Z/AZ，就表示PDA M在q0的状态下, 读过的符号为0，栈顶符号为Z时，就将栈顶符号改为AZ(A入栈)，同时 状态变为q1 。这就相当于δ(q0 ,0,Z)={(q1 ,AZ)。
下推自动机接受的语言
例 7.2 构造一个PDA M ,使其能以空栈方式接受语言L={ wcwR | w∈{0,1}* }。 令M =（{q1，q2 }，{0，1，c}，{R，B，G}，δ，q1 ，R， ），其中