Computer Science 456/656. Problem 1 of Assignment 9, Spring 2014.

1. True or False. T = true, F = false, and O = open, meaning that the answer is not known to science at this time.

(i) There exists a machine^{1} that runs forever and outputs the string of decimal digits of π (the well-known ratio of the circumference of a circle to its diameter).

(ii) For every real number x, there exists a machine that runs forever and outputs the string of

decimal digits of x. (iii) If a language has an unambiguous context-free grammar, then there must be some DPDA

that accepts it. (iv) The problem of whether two given context-free grammars generate the same language is

decidable.

(v) The problem of whether a given string is generated by a given context-free grammar is decidable.

(vi) The language {a^{n}b^{n}c^{n}d^{n} | n ≥ 0} is recursive. (vii) Let L be the language over {a, b, c} consisting of all strings which have more a’s than b’s

and more b’s than c’s. There is some PDA that accepts L. (viii) There exists a mathematical proposition that can be neither proved nor disproved. (ix) The language {a^{n}b^{n}c^{n} | n ≥ 0} is in the class P.

(x) There exists a polynomial time algorithm which finds the factors of any positive integer, where the input is given as a binary numeral.

(xi) Every undecidable problem is N P-complete. (xii) The problem of whether a given context-free grammar generates all strings is decidable. (xiii) The language {a^{n}b^{n} | n ≥ 0} is context-free. (xiv) The language {a^{n}b^{n}c^{n} | n ≥ 0} is context-free. (xv) The language {a^{i}b^{j}c^{k} | j = i + k} is context-free. (xvi) The intersection of any three regular languages is context-free. (xvii) If a language L is undecidable, then there can be no machine that enumerates L. (xviii) (Warning: this one is hard.) If f is any function on positive integers, there must be a

recursive function g such that f(n) = O(g(n)).

1As always in automata theory, “machine” means abstract machine, a mathematical object whose memory and running time are not constrained by the size and lifetime of the known (or unknown) universe, or any other physical laws. If we want to discuss the kind of machine that exists (or could exist) physically, we call it a “physical machine.”

(xix) Recall that if L is a class of languages, co-L is defined to be the class of all languages that are not

in L.

Let RE be the class of all recursively enumerable languages. If L is in RE and also L is in co-RE, then L must be decidable.

(xx) Every problem that can be mathematically defined has an algorithmic solution. (xxi) The intersection of two undecidable languages is always undecidable. (xxii) If L is N P and also co-N P, then L must be P. (xxiii) If L is a context-free language over an alphabet with just one symbol, then L is regular. (xxiv) Every N P language is decidable. (xxv) The intersection of two N P languages must be N P. (xxvi) The intersection of two N P-complete languages must be N P-complete. (xxvii) If G is a context-free grammar, the question of whether L(G) = ∅ is decidable. (xxviii) If G is a context-free grammar, the question of whether L(G) = Σ^{∗} is decidable, where Σ is

the terminal alphabet of G. (xxix) The set of all fractions whose values are less than π is decidable. (Think of a fraction as a

string of digits, followed by a slash, followed by another string of digits.) (xxx) There exists a polynomial time algorithm which finds the factors of any positive integer,

where the input is given as a unary numeral. (xxxi) Every bounded function is recursive. (xxxii) For any two languages L_{1} and L_{2}, if L_{1} is undecidable and there is a recursive reduction of

L_{1} to L_{2}, then L_{2} must be undecidable. (xxxiii) For any two languages L_{1} and L_{2}, if L_{2} is undecidable and there is a recursive reduction of

L_{1} to L_{2}, then L_{1} must be undecidable. (xxxiv) If P is a mathematical proposition that can be stated using n binary bits, and P has a proof,

then P must have a proof whose length is O(2^{2^{n}}). (xxxv) Let L be the language consisting of just one string of length 1, defined as follows:

L = \{ \begin{matrix}\{1\} if P = N P \\ \{0\} if P ≠ N P \end{matrix}

Then L is undecidable. (xxxvi) There is a P-time reduction of the context-free grammar membership problem to the halting

problem.