(状态转移表的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}是正则语言。