These are some of the formal languages portions of old MSCS comprehensive exams. See the file "read-me.txt" for more information. FALL 1989 COMPREHENSIVE EXAM COMPUTATION THEORY Each problem is worth 25 points; make sure that your answers are clear and focused. 1. Assume that L is an infinite recursively enumerable language. Show that there is a total recursive function f which enumerates L. That is L = {f(0), f(1), f(2), ..., f(n), ...) 2. Prove that L = ( | L(M) is empty ) is not a recursive language. 3. Prove that L = {(0**i)(1**i)(0**i)} is not a context free language. 4 Prove the existence of a language L which is not recursively enumerable. Theory of Computation Comprehensive Exam Spring, 1989 1. True or False: Scoring: One point for a right answer, -1 point for a wrong answer, 0 points for no answer. Minimum score zero, a. Every set recognizable by a finite automaton is regular. b. Every regular set is recognizable by a finite automaton. c. Every context- free language is recognizable by a finite automaton. d. Every non-deterministic finite automaton is equivalent to a deterministic finite automaton. e. Every (non-deterministic) pushdown automaton is equivalent to a deterministic pushdown automaton. f. Every Turing machine can be simulated by a pushdown automaton. g. Every pushdown automaton can be simulated by a Turing machine. h. Every recursive set is recognized by some Turing machine. 1. Every r.e. set is recognized by some Turing machine. j. Every r.e. set is recursive. k. Every recursive set is r.e. l. Every context-free language is r.e. m. Every regular set is recursive. n. Every context-free language is a regular set. o. The complement of a recursive set is recursive, p. The complement of an r.e. set is r.e. q. The complement of a regular set is regular, r. Every set in NP is recursive. s. Every set in P is recursive. t. Factoring an integer can be done in polynomial time. 2. Which of the following sets are regular over the alphabet {a, 6}*? a. {(a**n)(b**n) | n > 1} b. {a**n | n is divisible by 5} c. {wx | w is any word and x is its reverse} 3. Exhibit (the productions of) a context-free grammar which generates {(a**n)(b**n) | n > 1}. 4. The following rules of grammar are part of the speciEcation of Pascal. ::= ::= . For this exercise, assume that is a non-terminal and and the period (.) are terminals. Exhibit equivalent rules of grammar in which the left-recursion on is eliminated. 5. Which of the following expresses the "recursive unsolvability of the halting problem?" a. No Turing machine can halt when given its own program as input. b. No Turing machine can output 1 or 0 at input e, according as Turing machine e halts at input e or not. c. No Turing machine can compute whether it halts or not when given its own program as input. d. No Turing machine can output 1 at input e if and only if Turing machine e halts at input e. M.S. in Computer Science Comprehensive Exam 9-24-88 Theory of Computation The problems are worth 25 points each. The highest 4 of your answers will be counted. 1. Prove that 1(01)*0 and (10)+ represent the same language. 2. Find a regular grammar for the DFA whose transition function is given by the table below. The final states are q2 and q4. q0 q1 q2 q3 q4 0: q0 q2 q1 q4 q2 1: q1 q0 q3 q4 q4 3. A problem is semidecidable iff the set of instances for which the answer is "yes" is an r.e. set. Is it semidecidable, given an encoding for a Turing machine M, whether the empty string is in L(M)? Give two arguments to justify your answer. 4. Which of the following are decidable questions for CFGs? (a) whether a given x is in L(G) (b) whether L(G) is empty (c) whether the complement of L(G) is a CFL Justify your answers. 5. Give an example of a DCFL without the prefix property. Can this language be accepted by a DPDA by empty stack? Justify your answer. 6. Give an algorithm for constructing a grammar G from an instance of Post's Correspondence Problem (i.e., from two sequences of strings over a fixed alphabet) such that the grammar is ambiguous if and only if the instance has a solution. What does this imply about the question of whether G is ambiguous? PART II: Theory of Computation [S83] Do 3 of 5. 1. There are many ways of showing that a given language does or does not belong to a given class of languages. State as many results as you can. Give an example of a language which can be shown to belong to a particular class by such a result. Give a second example of a language which can be shown not to belong to a particular class. In both cases, give a brief justification of why the result you cite applies to your example. 2. Give a rigorous definition of undecidability. Give an example of an un- decidable problem and a sketch of the argument that shows it is undecidable. Does every recursively enumerable language correspond to a decidable pro- blem? Why or why not? 3. One may define both deterministic and non-deterministic versions of finite automata, pushdown automata, and Turing machines. In which cases do the non-deterministic versions accept more languages than the deterministic versions? In at least one case where this is not true, show how to con- struct a deterministic machine accepting the same language L(M) as a non- deterministic machine M. 4. Give examples of languages which are (a) regular (b) DCFL but not regular (c) CFL but not DCFL (d) recursive but not CFL (e) recursively enumerable but not recursive (f) not recursively enumerable. For two of your examples, give an argument to support your claim (except for (a) , your argument may be informal). 5. For as many classes of languages as you can, give descriptions of the grammars which generate and the automata which recognize languages in the class. Give at least one example of a method of constructing such a grammar from an automaton or such an automaton from a grammar.