7.1
(1)
(2)
7.2
8.1(1)
证明:对任意的k>=0,存在字符串z=a^kb^(k+1)c^(k+2);
综上:该语言不是CFL
8.4
aabbaa不属于L(G)
因为
-
D
S
-
-
A
a
9.2(1)
1.语言描述:
(1)读入并记录当前的符号(不是1:reject);
(2)将当前的符号改为X,;
(3)读写头右移,越过1和之后所有的Y,停在第一个0处(若找不到0:reject);
(4)将0改为Y;
(5)读写头左移,越过Y和1后,停在遇到的第一个x的右边;
(6)跳(1)直到右移下一个是Y(0都被标记完了)
(7)若读到1,将当前的符号改为X,右移越过所有的1,Y停在口左边;否则跳(9)
(8)跳(7)直到1被标记完
(9)右移,越过所有的Y
所有的1、0多被标记则接受。
2.截图:
9.2(5)
1.语言描述:
(1)读入并记录当前的符号;
(2)将当前的符号改为X;
(3)读写头右移,越过a,b,停在遇到的第一个Y或口的左边;
(4)将当前的符号(不一致:reject)改为Y;
(5)读写头左移,越过a和b后,停在遇到的第一个x的右边;
跳(1)直到右移的下一个是Y
如果所有的a和b都做过标记, 就accept
2.截图:
9.3(3)
1.语言描述:
输入:形如00000#0000,结果说明
(1)当纸带上只剩下X和#则结果为0
(2)当纸带上#左边有0结果为正(正几就看有几个0)
(3)当纸带上#右边有0结果为负(负几就看有几个0)
、、、、、、
过程描述:
(1)读入并记录当前的符号;
(2)将当前的符号改为X;
(3)读写头右移,越过0和过了#之后再越过所有的X,停在第一个0处;
(4)将0改为X;
(5)读写头左移,过了#后,再越过所有的0,停在遇到的第一个x的右边; X的右边为#则接受。
2.截图: