- 相關推薦
形式語言與自動機試題及答案
形式語言與自動機這門課程比較深奧，內容復雜，要學好這門課程不容易，同學們要用心去學才能學好形式語言與自動機。下面是陽光網小編給大家整理的形式語言與自動機試題及答案，歡迎大家學習參考。
形式語言與自動機試題及答案
《形式語言與自動機》期末測試題 (規定時間:2 小時)
1. (12 pts) 選擇填空(多選): (a) 由正規表達式 a* 定義的語言 ; A,C(或只回答 C) (b) 語言 {a m b m ?m ?0} ; B (c) 語言 {a m b m c m ?m ?0} ; D (d) 語言 {a m b n c m ?m,n ?0} ; B (e) 對角化(diagonalization)語言 L d ;F (f) 通用語言(universal)語言 L u ;E 供選擇的答案: A. 是某個有限狀態自動機的語言; B. 是某個下推自動機的語言, 但不是任何有限狀態自動機的語言; C. 是某個有限狀態自動機的語言,但不是任何空棧接受方式的確定下推自動機的語言; D. 是某個可停機的圖靈機的語言, 但不是任何下推自動機的語言; E. 是某個圖靈機的語言, 但不是任何可停機的圖靈機的語言; F. 不是任何圖靈機的語言. 2. (7 pts) 圖靈機({ q 0 , q 1 , q 2 , q 3 }, { 0,1 }, { 0,1,B }, ?, q 0 , B, {q 3 })有如下轉移規則: ?(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開始, 該圖靈機可以到達的完整的ID序列, 直到它停機 . 3. (12 pts) 設有四個語言(或問題)A，B，C 和 D. 這些語言可以是，也可以不是遞歸可 枚舉語言，但已知如下條件: (此題出得不好) i. A 可以歸約到 B(不一定是多項式時間歸約，下同); ii. B 可以歸約到 C; iii. D 可以歸約到 C; 對于以下 6 個命題，分別指出它們是“真”，或是“假”，或是“不能確定”: (a) A 是遞歸可枚舉的但不是遞歸的，而 C 是遞歸的`. 假(A 不是遞歸的與C是遞 歸的不可能同時成立) (b) B 不是遞歸的，而 D 是遞歸可枚舉的. 不能確定 (c) A 的補不是遞歸可枚舉的，而 B 的補是遞歸可枚舉的. 不能確定 (d) B 的補不是遞歸的，而 C 的補是遞歸的. 假 (e) 如果 A 是遞歸的，那么 B 的補是遞歸的. 不能確定 (f) 如果 C 是遞歸的，那么 D 的補是遞歸的. 真
猜你喜歡：
【形式語言與自動機試題及答案】相關文章：
經典力學試題試題試題及答案04-02
熱學試題及答案04-02
電子測量試題及答案-《電子測量》期末復習試題及答案04-01
電氣測量試題及答案-《電氣測量》期末復習試題及答案04-02
外企面試經典的試題及答案12-09
外企面試的經典的試題及答案12-09
經典面試題及答案04-04
面試題及答案04-04
概率統計試題及答案04-02