形式語(yǔ)言與自動(dòng)機(jī)試題及答案

　　形式語(yǔ)言與自動(dòng)機(jī)這門(mén)課程比較深?yuàn)W，內(nèi)容復(fù)雜，要學(xué)好這門(mén)課程不容易，同學(xué)們要用心去學(xué)才能學(xué)好形式語(yǔ)言與自動(dòng)機(jī)。下面是陽(yáng)光網(wǎng)小編給大家整理的形式語(yǔ)言與自動(dòng)機(jī)試題及答案，歡迎大家學(xué)習(xí)參考。

　　形式語(yǔ)言與自動(dòng)機(jī)試題及答案

　　《形式語(yǔ)言與自動(dòng)機(jī)》期末測(cè)試題 (規(guī)定時(shí)間:2 小時(shí))

　　1. (12 pts) 選擇填空(多選): (a) 由正規(guī)表達(dá)式 a* 定義的語(yǔ)言 ; A,C(或只回答 C) (b) 語(yǔ)言 {a m b m ?m ?0} ; B (c) 語(yǔ)言 {a m b m c m ?m ?0} ; D (d) 語(yǔ)言 {a m b n c m ?m,n ?0} ; B (e) 對(duì)角化(diagonalization)語(yǔ)言 L d ;F (f) 通用語(yǔ)言(universal)語(yǔ)言 L u ;E 供選擇的答案: A. 是某個(gè)有限狀態(tài)自動(dòng)機(jī)的語(yǔ)言; B. 是某個(gè)下推自動(dòng)機(jī)的語(yǔ)言, 但不是任何有限狀態(tài)自動(dòng)機(jī)的語(yǔ)言; C. 是某個(gè)有限狀態(tài)自動(dòng)機(jī)的語(yǔ)言,但不是任何空棧接受方式的確定下推自動(dòng)機(jī)的語(yǔ)言; D. 是某個(gè)可停機(jī)的圖靈機(jī)的語(yǔ)言, 但不是任何下推自動(dòng)機(jī)的語(yǔ)言; E. 是某個(gè)圖靈機(jī)的語(yǔ)言, 但不是任何可停機(jī)的圖靈機(jī)的語(yǔ)言; F. 不是任何圖靈機(jī)的語(yǔ)言. 2. (7 pts) 圖靈機(jī)({ q 0 , q 1 , q 2 , q 3 }, { 0,1 }, { 0,1,B }, ?, q 0 , B, {q 3 })有如下轉(zhuǎn)移規(guī)則: ?(q 0 , 0)=(q 1 ,1, R) ?(q 1 , 1)=(q 2 , 0, L) ?(q 2 , 1)=(q 0 , 1, R) ?(q 1 , B)=(q 3 , B, R) 給出從初始ID q 0 0110開(kāi)始, 該圖靈機(jī)可以到達(dá)的完整的ID序列, 直到它停機(jī) . 3. (12 pts) 設(shè)有四個(gè)語(yǔ)言(或問(wèn)題)A，B，C 和 D. 這些語(yǔ)言可以是，也可以不是遞歸可 枚舉語(yǔ)言，但已知如下條件: (此題出得不好) i. A 可以歸約到 B(不一定是多項(xiàng)式時(shí)間歸約，下同); ii. B 可以歸約到 C; iii. D 可以歸約到 C; 對(duì)于以下 6 個(gè)命題，分別指出它們是“真”，或是“假”，或是“不能確定”: (a) A 是遞歸可枚舉的但不是遞歸的，而 C 是遞歸的`. 假(A 不是遞歸的與C是遞 歸的不可能同時(shí)成立) (b) B 不是遞歸的，而 D 是遞歸可枚舉的. 不能確定 (c) A 的補(bǔ)不是遞歸可枚舉的，而 B 的補(bǔ)是遞歸可枚舉的. 不能確定 (d) B 的補(bǔ)不是遞歸的，而 C 的補(bǔ)是遞歸的. 假 (e) 如果 A 是遞歸的，那么 B 的補(bǔ)是遞歸的. 不能確定 (f) 如果 C 是遞歸的，那么 D 的補(bǔ)是遞歸的. 真

　　猜你喜歡：

1.形式語(yǔ)言與自動(dòng)機(jī)試題及答案

2.熱力發(fā)電廠(chǎng)試題及答案

3.射頻電路設(shè)計(jì)試題及答案

【形式語(yǔ)言與自動(dòng)機(jī)試題及答案】相關(guān)文章：

經(jīng)典力學(xué)試題試題試題及答案04-02

熱學(xué)試題及答案04-02

電子測(cè)量試題及答案-《電子測(cè)量》期末復(fù)習(xí)試題及答案04-01

電氣測(cè)量試題及答案-《電氣測(cè)量》期末復(fù)習(xí)試題及答案04-02

外企面試經(jīng)典的試題及答案12-09

外企面試的經(jīng)典的試題及答案12-09

經(jīng)典面試題及答案04-04

面試題及答案04-04

概率統(tǒng)計(jì)試題及答案04-02