CT计算理论试卷(2003)v2.doc

浙江大学2003 2004学年第二学期期终考试The Theory of Computation课程试卷考试时间：_120_分钟 开课学院 计算机学院 专业 姓名_ 学号_任课教师_题序1234567总分评分评阅人1. (20pts, 2 each) Tell whether the statements below are true (T) or false (F).(1) ( ) Language a6nb3mcn+10 : n 0, m 0 is regular.(2) ( ) A and B are two context-free languages, so is AB, where AB =(A-B)(B-A).(3) ( ) Let L1, L2 Li are all regular languages, so is .(4) ( ) Suppose that L is context-free and R is regular, L-R is context-free language.(5) ( ) A language is recursive if and only if its complement is recursive enumerable.(6) ( ) Every computable function is primitive recursive.(7) ( ) Turing Machines with two-way infinite tape accept more languages than the standard Turing Machines.(8) ( ) Every Turing machine semidecides a recursive language.(9) ( ) L is a language, then L=.(10) ( ) L is a language, there is a Turing machine M halts on x for every xL, then L is decidable.2. Automata and regular expressions:(1) (8pts) Give a NFA (Nondeterministic Finite Automaton) accepting the language L=x | xa, b* and aab occurs as substring of x at least twice. Draw a state transition diagram of the NFA and simplify as much as possible.(2) (8pts) Write a regular expression for the language accepted by the following finite automaton:3. Pushdown Automata (PDA) and Context-free Grammar (CFG):(1) (8pts) Give a CFG that generates the L=uuRcvvR | u,va,b*.(2) (8pts) Design a PDA M=(K, , G, D, s, F) accepting the language above , whereD:(q, a, b)(q, b)=a, b;K=G=s=F=4. Say whether each of the following languages is regular or not regular (prove your answers):(1) (8pts) L1=xy | x, ya, b*, #x(a) = #y(b). Note: #x(a) presents the number of a in string x, #y(b) so on.(2) (8pts) L2=w: wa, b* and w=wR 5. (8pts) Give the equivalent primitive recursive function from the predicate x=y.6. (8pts) Let be an alphabet and let L1, L2 * be languages so that L1 is not regular but L2 is regular. Assume L1L2 is finite, Prove that L1L2 is not regular.0,1;L1SR0,10,1R L010L1100LLRL7. Let the following Turing machine M computes f(x, y), the alphabet is = 0, 1, ;. The head of M begins from the most left blank; 0 is the symbol of blank; x and y are presented by binary strings respectively and separated with the symbol “;”.(1) (8pts) Describe the key configurations