程序設(shè)計(jì)語言基礎(chǔ)答案

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ī)表達(dá)式是__(14)__。(14)A.abbB.aabbC.aabD.ab●一個(gè)文法G=(N，T，P，S)，其中N是非終結(jié)符號的集合，T是終結(jié)符號的集合，P是產(chǎn)生式

2、集合，S是開始符號，令集合V=N∪T，那么G所描述的語言是__(15)__的集合。(15)A由S推導(dǎo)出的所有符號串B由S推導(dǎo)出的所有終結(jié)符號串CV中所有符號組成的符號串DV的閉包中的所有符號串●下圖為一確定有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖，與該自動(dòng)機(jī)等價(jià)的正規(guī)表達(dá)式是__（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)換圖中，每一個(gè)結(jié)點(diǎn)代表一個(gè)狀態(tài)，其中雙圈是終結(jié)狀態(tài)。該題實(shí)際上是一個(gè)簡化確定有限自動(dòng)機(jī)(DFA)的過程，一個(gè)確定有限自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有限自動(dòng)機(jī)。首先介紹2個(gè)概念：最小狀態(tài)DFA和等價(jià)狀態(tài)。最小狀態(tài)DFA必須滿足以下2個(gè)條件。(1)沒有多余狀態(tài)(死狀態(tài))：多余狀態(tài)從該自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串都不能到達(dá)的那個(gè)狀態(tài)。(2)

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

5、句，都是程序中控制流程無法到達(dá)的語句，從而也是不會(huì)被執(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