形式語言自動(dòng)機(jī)

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)
7.2（5）

7.4

8.1(1)

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

        而無論z=uvwxy;如何的劃分；存在五種情況：

        1. vx在a^k內(nèi)：令i的值取大于零的數(shù)則字符串中a的個(gè)數(shù)>=b的個(gè)數(shù)，新的字符串就不在L中了；

        2. vx在b^(k+1)：令i的值取大于零的數(shù)則字符串中b的個(gè)數(shù)>=c的個(gè)數(shù)，新的字符串就不在L中了；

        3. vx在c^(k+2)內(nèi)：令i的值取零的數(shù)則字符串中b的個(gè)數(shù)>=c的個(gè)數(shù)，新的字符串就不在L中了；

        4. v 在a^k內(nèi)，x在b^(k+1)內(nèi)：令i的值取大于零的數(shù)則字符串中a的個(gè)數(shù)>=c的個(gè)數(shù)或b的個(gè)數(shù)>=c的個(gè)數(shù)，新的字符串就不在L中了；

        5. v在b^(k+1)內(nèi)，x在c^(k+2)內(nèi)：令i的值取大于零的數(shù)則字符串中a的個(gè)數(shù)>=c的個(gè)數(shù)或a的個(gè)數(shù)>=b的個(gè)數(shù)，新的字符串就不在L中了；

綜上：該語言不是CFL

8.4

aabbaa不屬于L(G)

因?yàn)?/p>

-

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）讀入并記錄當(dāng)前的符號(hào)（不是1：reject）；

（2）將當(dāng)前的符號(hào)改為X，；

（3）讀寫頭右移，越過1和之后所有的Y，停在第一個(gè)0處（若找不到0：reject）；

（4）將0改為Y；

（5）讀寫頭左移，越過Y和1后，停在遇到的第一個(gè)x的右邊；

（6）跳（1）直到右移下一個(gè)是Y（0都被標(biāo)記完了）

（7）若讀到1，將當(dāng)前的符號(hào)改為X，右移越過所有的1，Y停在口左邊；否則跳（9）

（8）跳（7）直到1被標(biāo)記完

（9）右移，越過所有的Y

所有的1、0多被標(biāo)記則接受。

2.截圖：

9.2(5)

1.語言描述：

（1）讀入并記錄當(dāng)前的符號(hào)；

（2）將當(dāng)前的符號(hào)改為X；

（3）讀寫頭右移，越過a,b，停在遇到的第一個(gè)Y或口的左邊；

（4）將當(dāng)前的符號(hào)（不一致：reject）改為Y；

（5）讀寫頭左移，越過a和b后，停在遇到的第一個(gè)x的右邊；

跳（1）直到右移的下一個(gè)是Y

如果所有的a和b都做過標(biāo)記, 就accept

2.截圖：

9.3(3)

1.語言描述：

輸入：形如00000#0000，結(jié)果說明

（1）當(dāng)紙帶上只剩下X和#則結(jié)果為0

（2）當(dāng)紙帶上#左邊有0結(jié)果為正（正幾就看有幾個(gè)0）

（3）當(dāng)紙帶上#右邊有0結(jié)果為負(fù)（負(fù)幾就看有幾個(gè)0）

、、、、、、

過程描述：

（1）讀入并記錄當(dāng)前的符號(hào)；

（2）將當(dāng)前的符號(hào)改為X；

（3）讀寫頭右移，越過0和過了#之后再越過所有的X，停在第一個(gè)0處；

        若無0，則左移，過了#后，還原第一個(gè)X，并接受；

（4）將0改為X；

（5）讀寫頭左移，過了#后，再越過所有的0，停在遇到的第一個(gè)x的右邊； X的右邊為#則接受。

2.截圖：