Write T for true, F for false, and O for open, i.e., the answer is not known to science at this time. 1. The union of any collection of regular languages is regular. 2. If f is a function from strings to strings, and if f can be computed in polynomial time, then an inverse function of f can always be computed in polynomial time. Definition: g is an inverse function of f if the following two conditions hold: 1) If g(y) is not the empty string, then f(g(y)) = y. 2) If f(x) = y, then g(y) = z for some z such that f(z) = y. (Note that this agrees with the usual definition of inverse function if f is one-to-one and onto.) 3. If a language is NP, then it must be either in P, or be NP-complete. 4. A bottom-up parser constructs the parse tree of a string in reverse postorder. 5. A top-down parser constructs the parse tree of a string in preorder. 6. The complement of any context-free language is context-free. 7. Every recursively enumerable language that is NOT recursive is NP-complete. 8. If P is not equal to NP, then RSA encryption is secure, i.e., given the public key, it takes exponential time to find the private key. 9. Every context-free language is NP. 10. The complement of any recursive language is recursive. 11. The complement of any recursively enumerable language is recursively enumerable. 12. The well-known number pi, the ratio of the circumference of a circle to its diameter, is a recursive real number. (We say that a real number x is "recursive" if there is a machine that runs forever, writing the decimal digits of x to the output stream.) 13. Suppose there is a machine that runs forever, writiing a sequence of rational numbers which converges to a certain real number x. Then, x must be a recursive real number. 14. Every context-free language is P. 15. Suppose we can prove there is a recursive reduction of a certain language L to the universal language (i.e., the halting problem). Then L must be undecidable. 16. Every recursive language is generated by a general grammar. 17. Every non-empty context-free language has an ambiguous context-free grammar. 18. Every recursively enumerable language is generated by a general grammar. 19. P = NC. 20. Every context-free language is NC. 21. Every language is enumerable.