程序設計語言基礎答案

1、●已知文法G[S]:S→A0|Bl，A→S1|1，B→S0|0；該文法屬于喬姆斯基定義的__(12)__文法，它不能產(chǎn)生串__(13)__。(12)A.0型B.1型C.2型D.3型(13)A.0011B.1010C.1001D.0101●語言L=ambn|m≥0，n≥1的正規(guī)表達式是__(14)__。(14)A.abbB.aabbC.aabD.ab●一個文法G=(N，T，P，S)，其中N是非終結(jié)符號的集合，T是終結(jié)符號的集合，P是產(chǎn)生式

2、集合，S是開始符號，令集合V=N∪T，那么G所描述的語言是__(15)__的集合。(15)A由S推導出的所有符號串B由S推導出的所有終結(jié)符號串CV中所有符號組成的符號串DV的閉包中的所有符號串●下圖為一確定有限自動機的狀態(tài)轉(zhuǎn)換圖，與該自動機等價的正規(guī)表達式是__（12）__，圖中的__（13）__是可以合并的狀態(tài)。（12）A.(a|b)bb(ab)B.(a|b)bba|bC.(ab)bb(a|b)D.(a|b)bb(a|b)（13）A.

3、0和1B.2和3C.1和2D.0和3正確答案：A解析：在狀態(tài)轉(zhuǎn)換圖中，每一個結(jié)點代表一個狀態(tài)，其中雙圈是終結(jié)狀態(tài)。該題實際上是一個簡化確定有限自動機(DFA)的過程，一個確定有限自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有限自動機。首先介紹2個概念：最小狀態(tài)DFA和等價狀態(tài)。最小狀態(tài)DFA必須滿足以下2個條件。(1)沒有多余狀態(tài)(死狀態(tài))：多余狀態(tài)從該自動機的開始狀態(tài)出發(fā)，任何輸入串都不能到達的那個狀態(tài)。(2)

4、沒有2個狀態(tài)是互相等價(不可區(qū)別)。2個狀態(tài)s和t如果同時滿足下列2個條件，就稱s和t是等價的。(1)一致性：同是終態(tài)或同是非終態(tài)。(2)蔓延性：從s出發(fā)讀人某個a和從t出發(fā)讀入某個a到達的狀態(tài)等價。本題的簡化過程如下：①由該人口語句到另一入口語句(不包括該入口語句)之間的語句序列；②由該人口語句到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)之間的語句序列；③由該人口語句到一停轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)之間的語句序列。(3)凡是未被納入某一基本塊中的語

5、句，都是程序中控制流程無法到達的語句，從而也是不會被執(zhí)行到的語句，可以從程序中刪除。在本題中，根據(jù)程序求解。(1)確定入口。A：=100入口j：=100i：=1loop1：B：=j1入口C：=BIA：=ACifi=100gotoloop2i：=i1入口goto100p1100p2：writeA入口halt停語句(2)確定基本塊?；緣K1A：=00入口j：=100i：=1基本塊2loop1：B：=j1入口C：=BIA：=ACifi=100