形式语言自动机

7.1

(1)

       (q0,bab,Z0)┣(q2,ab,BZ0)┣(q3,b,Z0)不接受

       (q0,abb,Z0)┣(q1,bb,AAZ0)┣(q1,b,AZ0)┣(q1,ε,Z0)┣(q0,ε,Z0)┣(f,ε,ε)接受

(2)

     |BBZ0|

7.2

(1)

8.1(1)

证明：对任意的k>=0,存在字符串z=a^kb^(k+1)c^(k+2);

        而无论z=uvwxy;如何的划分；存在五种情况：

        1. vx在a^k内：令i的值取大于零的数则字符串中a的个数>=b的个数，新的字符串就不在L中了；

        2. vx在b^(k+1)：令i的值取大于零的数则字符串中b的个数>=c的个数，新的字符串就不在L中了；

        3. vx在c^(k+2)内：令i的值取零的数则字符串中b的个数>=c的个数，新的字符串就不在L中了；

        4. v 在a^k内，x在b^(k+1)内：令i的值取大于零的数则字符串中a的个数>=c的个数或b的个数>=c的个数，新的字符串就不在L中了；

        5. v在b^(k+1)内，x在c^(k+2)内：令i的值取大于零的数则字符串中a的个数>=c的个数或a的个数>=b的个数，新的字符串就不在L中了；

综上：该语言不是CFL

8.4

aabbaa不属于L(G)

因为

-

D   D

S   S    S

-    C    -    D

-    S    -    S    -

A    A   B    B   A   A

a    a    b    b   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处；

        若无0，则左移，过了#后，还原第一个X，并接受；

（4）将0改为X；

（5）读写头左移，过了#后，再越过所有的0，停在遇到的第一个x的右边； X的右边为#则接受。

2.截图：