15年真题(1) (1).pdf

发布时间：2022-06-12 发布人：admin 分类：说明书资料大小：0.46M 资料格式：pdf 举报版权申诉

155b96f9-b56d-4e4f-93ca-f22dce0b97d8.pdf-第1页.png

第1页 / 共6页

155b96f9-b56d-4e4f-93ca-f22dce0b97d8.pdf-第2页.png

第2页 / 共6页

155b96f9-b56d-4e4f-93ca-f22dce0b97d8.pdf-第3页.png

第3页 / 共6页

155b96f9-b56d-4e4f-93ca-f22dce0b97d8.pdf-第4页.png

第4页 / 共6页

155b96f9-b56d-4e4f-93ca-f22dce0b97d8.pdf-第5页.png

第5页 / 共6页

155b96f9-b56d-4e4f-93ca-f22dce0b97d8.pdf-第6页.png

第6页 / 共6页

文本预览

学院计算机科学与技术专业计算机科学与技术班年级学号姓名共 6 页第 1 页 A 天津大学试卷专用纸 3. (5 分) Give the state diagram of a DFA recognizing the following language. Σ {a, b} {w | w does not contains the substring baba} (Note that you cannot give an NFA.) 4. (5 分) Convert the NFA M1 in Problem 1 to an equivalent DFA. 2014～2015 学年第 2 学期期末考试试卷《形式语言与自动机》（A 卷共 6 页）（考试时间：2015 年 6 月 26 日）题号一二三四成绩核分人签字得分一、Finite Automata and Regular Languages（50 分） 1. (5 分) Given the following state diagram of a NFA M1 (1) Please write out the formal 5-tuple definition of M1. (2) What is the language of M1, i.e., L(M1)? 2. (5 分) Give the state diagram of a DFA recognizing the following language. Σ {a, b} {w | w starts with an a and has at most one b}

学院计算机科学与技术专业计算机科学与技术班年级学号姓名共 6 页第 2 页 A 天津大学试卷专用纸 5. (5 分) Convert the following regular expression to an NFA. 6. (10 分) Convert the following DFA to a regular expression.

学院计算机科学与技术专业计算机科学与技术班年级学号姓名共 6 页第 3 页 A 天津大学试卷专用纸 7. (5 分) Use the pumping lemma to prove that the following language is not regular. 二、Formal Languages（30 分） { | } 9. (5 分) Given the following RG 8. (10 分) Prove that the following language is not regular. j L {ab j | j c i 0} {a j b k | i, j, k 0 i c 1} (Hint: using proof by contradiction) Give a finate automaton which is equivalent to the RG. 10. (5 分) Given the following DFA Give an RG which is equivalent to the DFA. 21n0n

学院计算机科学与技术专业计算机科学与技术班年级学号姓名共 6 页第 4 页 A 11. (5 分) Given the following CFG 13. (10 分) Convert the following CFG into an equivalent CFG in Chomsky normal form. 天津大学试卷专用纸 Show the parse tree for the string (a+a) a 12. (5 分) Give the state diagram of a PDA that recognizes the following language. {0n1n | } 0n

天津大学试卷专用纸学院计算机科学与技术专业计算机科学与技术班年级学号姓名共 6 页第 5 页 A 三、Turing Machines（10 分） 14. (10 分) Given the state diagram of the Turing machine that recognizes the language (2) Give a run of this machine on input string 0000 by writing out a sequence of configurations. The first configuration in the sequence is the start configuration q10000, and the last configuration in the sequence is the accepting configuration xxx qaccept. Please write out the remaining configurations in the sequence. { | } ○1 q10000 ○7 ___________ ○13 ___________ ○19 ___________ ○2 __________ ○8 ___________ ○14 ___________ ○20 ___________ ○3 ___________ ○9 ___________ ○15 ___________ ○21 ___________ ○4 ___________ ○10 ___________ ○16 ___________ ○22 xxx qaccept (1) Give the formal 7-tuple definition of the above Turing machine ○6 ___________ ○12 ___________ ○18 ___________ ○5 ___________ ○11 ___________ ○17 ___________ 20n0n

学院计算机科学与技术专业计算机科学与技术班年级学号姓名共 6 页第 6 页 A 天津大学试卷专用纸四、Proofs（10 分） 15. (10 分) An all-NFA M is a 5-tuple (Q, Σ, δ, q0, F) that accepts if every possible state that M could be in after reading input x is a state from F. Note, in contrast, that an ordinary NFA accepts a string is some state among these possible states is an accept state. Prove that all-NFAs recognize the class of regular languages. *x

分享到：

赞收藏

资料库

15年真题(1) (1).pdf

相关推荐

课程资源

热门标签

最新资料