X…X0…0 Y…Y1…1Z…ZZ…ZBB X…X0…0 Y…YY…YZ…ZZ…ZBB
Y / YZ / ZY / YZ / ZX / Xq5B / Bq6Startq00 / Xq11 / Yq22 / Zq3Y / Y0 / 0Z / Z1 / 1Z / Z1 / 1Y / Y0 / 0q4（2）{ω|ω∈{0，1}*,ω含有相同个数的0和1}。 (注意与P224例8.2中0n1n的区别) 下面是转移函数表
state 0 1 B - - - X Y (q0,Y,R) (q1,Y,R) (q2,Y,R) - q0 (q2,X,R) (q1,X,R) (qf,B,R) - q1 (q3,Y,L) (q1,1,R) - q2 (q2,0,R) (q3,Y,L) - q3 (q3,0,L) (q3,1,L) - qf - - - (q0,X,R) (q3,Y ,L) 思路是TM(图灵机)沿着带子不断地向后和向前游历.符号X 和 Y用来替代已经
相互抵消了的0和1.差别在于，X保证其左侧没有不能匹配的0和1，因此带头从不移到X的左侧。但是 Y的左侧可能有0和1。对照转移表，下面说明每个转移的含义.
(状态转移表的q0行) 起初在状态q0，TM读到一个0或1，将其记在状态里(q1=读到一个1；q2=读到一个0)，并将所读到的用一个X抵消(也就是用X替换0或1).有一个例外，如果TM在状态q0看到空格，则所有0和1已匹配，因此进入状态qf输入被接受.
(状态转移表的q0行和q1行)在状态q1，TM向右移，寻找一个0.如果找到了，用Y 代替0，TM进入状态q3向左移寻找一个X.类似地，状态q2寻找一个1来匹配0.
(状态转移表的q3行)在状态q3, TM向左移直至找到最右边的X.此时，又一次进入状态q0，向右移穿过Y直至找到0，1，或空格，循环又一次开始. 6．设A=(Q,Σ,δ,q0,F)为DFA，证明：PPT正则语言的性质
（1）L=L(A)非空的充分必要条件是存在x∈Σ*,使得且δ*(q0,x)∈F,|x|<|Q|
（2）L=L(A)为无穷集的充分必要条件是，存在x∈Σ*，使得|Q|≤|x|<2|Q|且δ*(q0,x) ∈F,其中|Q|表示状态集Q的元素个数，|x|表示串x的长度。
============================================================= 7．讨论并论证上下文无关语言关于交运算的封闭性，以及上下文无关语言与正则语言的交运算的性质(PPT第8章54页)。 定理 8-2 CFL 在交运算下不封闭的。
设 L1={ 0n1n2m | n, m≥1 }，L2={ 0n1m2m | n, m≥1 }。
G1：S1?AB 显然，L(G1)=L1、L(G2)=L2 。
A?0A1|01 L= L1∩L2 = { 0n1n2n | n≥1} 不是 CFL。 B?2B|2 所以，CFL 在交运算下是不封闭的。
G2：S?AB
A?0A|0 B?1B2|12
8．设L是字母表Σ上的正则语言，a∈Σ，证明：商Σ/a={ω∈Σ*|ωa∈L}也是正则语言。
证明：若L是任一正则语言，设接受L的DFA 为A＝ (Q,Σ,δ,q0, F) ，据此可以构造另一台DFA B＝(Q,Σ,δ,q0, F1)，其中前四项与A相同，而取 F1＝{q| ??(q,a)?F}，
则B是接受的正则语言，即商Σ/a={ω∈Σ*|ωa∈L}是正则语言。
相关推荐：
loading