CS 373 Theory of Computation 1. Prove that if a language is recursive, then its complement is also recursive. 2. Prove that the set of all languages that are not recursively enumerable is not...

This is a set of 9 questions in Theory of Computation. As needed, you could use diagrams such as a black-box with input and outputs that represent procedures and algorithms


CS 373 Theory of Computation 1. Prove that if a language is recursive, then its complement is also recursive. 2. Prove that the set of all languages that are not recursively enumerable is not countable. 3. Assume that a procedure is formalized as a Turing machine that can be represented as a finite length string from a finite alphabet. Thus any string over this alphabet is a Turing machine. Is the set of all Turing machines countable? Explain. Give an effective enumeration of all Turing machines (that is, describe a “procedure” that will list all Turing machines). 4. Prove Cantor’s original result: for any nonempty set (whether finite or infinite), the cardinality of S is strictly less than that of its power set 2S. First show that there is a one-to-one (but not necessarily onto) map g from S to its power set. Next assume that there is a one-to-one and onto function f and show that this assumption leads to a contradiction by defining a new subset of S that cannot possibly be the image of the map f (similar to the diagonalization argument). 5. Consider the grammar { } { } ),,,,,,( SPbaBASG = with P: S -> aB | bA A -> aS | bAA | a B -> bS | aBB | b What is L(G)? Outline the reasons for your claim. What type of grammar is this? 6. A string of parentheses is balanced if each left parenthesis, [, has a matching right parenthesis, ]. Find a grammar that generates the set of balanced strings of parentheses. An example of such a string is [[]][]. 7. Find grammars that generate the following languages: (a) L = {anbmambn : n, m ≥ 0} where V = {a, b}. (b) L = {w: |w| mod 3 ≤ |w| mod 2} where V = {a}. 8. Use induction on the size of S to show that if S is a finite set, then |2S| = 2|S|. 9. Show that if L1 and L2 are recursive languages, then the union of the two languages is a recursive language.