形式语言自动机

7.1

(1)

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

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

(2)

|BBZ0|

7.2

(1) 7.2（5） 7.4

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.截图：

-电子元器件采购网（www.ruidan.com）是本土元器件目录分销商，采用“小批量、现货、样品”销售模式，致力于满足客户多型号、高质量、快速交付的采购需求。 自建高效智能仓储，拥有自营库存超过50,000种，提供一站式正品现货采购、个性化解决方案、选型替代等多元化服务。