CS 456 Larmore T/F

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.

F

The language {aⁿbⁿ | n >= 0} is context-free.

T

The language {aⁿbⁿcⁿ | n >= 0} is context-free.

F

The language {aⁱb^jc^k | n >= 0} is context-free.

T

The intersection of any three regular languages is regular

T

The intersection of any regular language with any context-free language is context-free.

T

The intersection of any two context-free languages is context-free.

F

If L is a context-free language over an alphabet with just one symbol, then L is regular.

T

There is a deterministic parser for any context-free grammar. (But not necessarily an LALR parser.)

T

The set of strings that your high school algebra teacher would accept as legitimate expressions is a context-free language.

T

Every language accepted by a non-deterministic machine is accepted by some deterministic machine

T

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

T

If G is a context-free grammar, the question of whether L(G) = ∅ is decidable.

T

Every language generated by an unambiguous context-free grammar is accepted by some DPDA.

F

The language {aⁿbⁿcⁿdⁿ | n >= 0} is recursive

T

The language {aⁿbⁿcⁿ | n >= 0} is in the class P-time.

T

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

O

Every undecidable problem is N P-complete.

F

Every problem that can be mathematically defined has an algorithmic solution.

F

The intersection of two undecidable languages is always undecidable.

F

Every NP language is decidable.

T

The intersection of two N P languages must be N P.

T

If L1 and L2 are N P-complete languages and L1 ∩ L2 is not empty, then L1 ∩ L2 must be N P-complete.

F

N C = P.

O

P = NP.

O

N P = P-space

O

P-space = EXP-time

O

EXP-time = EXP-space

O

EXP-time = P-time.

F

EXP-space = P-space.

F

The traveling salesman problem (TSP) is NP-complete

T

The knapsack problem is NP-complete.

T

The language consisting of all satisfiable Boolean expressions is NP-complete.

T

The Boolean Circuit Problem is in P.

T

The Boolean Circuit Problem is in N C.

O

If L1 and L2 are undecidable langugages, there must be a recursive reduction of L1 to L2.

F

The language consisting of all strings over {a, b} which have more a’s than b’s is LR(1).

T

2-SAT is P-time.

T

3-SAT is P-time.

O

Primality is P-time.

T

There is a P-time reduction of the halting problem to 3-SAT.

T

Every context-free language is in P.

T

Every context-free language is in N C.

O

Addition of binary numerals is in N C.

T

Every context-sensitive language is in P.

O

Every language generated by a general grammar is recursive.

F

The problem of whether two given context-free grammars generate the same language is decidable.

F

The language of all fractions (using base 10 numeration) whose values are less than π is decidable.

T

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

T

For any two languages L1 and L2, if L1 is undecidable and there is a recursive reduction of L1 to L2, then L2 must be undecidable.

T

For any two languages L1 and L2, if L2 is undecidable and there is a recursive reduction of L1 to L2, then L1 must be undecidable.

F

If P is a mathematical proposition that can be written using a string of length n, and P has a proof, then P must have a proof whose length is O(22 n ).

F

If L is any N P language, there must be a P–time reduction of L to the partition problem.

T

Every bounded function is recursive.

F

If L is N P and also co-N P, then L must be P

O

If L is RE and also co-RE, then L must be decidable.

T

Every language is enumerable.

T

If a language L is undecidable, then there can be no machine that enumerates L.

F

There exists a mathematical proposition that can be neither proved nor disproved

T

There is a non-recursive function which grows faster than any recursive function.

T

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

T

For every real number x, there exists a machine that runs forever and outputs the string of decimal digits of x.

F

Rush Hour, the puzzle sold in game stores everywhere, generalized to a board of arbitrary size, is N P–complete

O

There is a polynomial time algorithm which determines whether any two regular expressions are equivalent.

O

If two regular expressions are equivalent, there is a polynomial time proof that they are equivalent.

O

Every subset of a regular language is regular.

F

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.

F

Every subset of any enumerable set is enumerable.

T

If L is a context-free language which contains the empty string, then L\{λ} must be context-free.

T

If L is any language, there is a reduction of L to the halting problem. (Warning: this is a trick question. Give it some serious thought.)

T

The computer language C++ has Turing power.

T

Let Σ be the binary alphabet. Every w ∈ Σ ∗ which starts with 1 is a binary numeral for a positive integer. Let Sq : Σ∗ → Σ∗ be a function which maps the binary numeral for any integer n to the binary numeral for n 2 . Then Sq is an N C function.

T

If L is any P-time language, there is an N C reduction of the Boolean circuit problem to L.

T

If an abstract Pascal machine can perform a computation in polynomial time, there must be some Turing machine that can perform the same computation in polynomial time.

T

The binary integer factorization problem is co-N P.

T

Let L be any RE language which is not decidable, and let ML be a machine which accepts L.

(a) If there are no strings of L of length n, let T(n) = 0.

(b) Otherwise, let T(n) be the largest number of steps it takes ML to accept any string in L of length n.

Then T is a recursive function

F

There is a polynomial time reduction of the subset sum problem to the binary factorization problem.

O

The language of all palindromes over {a, b} is an LR language.

F

The Simplex algorithm for linear programming is polynomial time.

F

Remember what a fraction is? It’s a string consisting of a decimal numberal, followed by a slash, followed by another decimal numeral whose value is not zero. For example, the string “14/37” is a fraction. Each fraction has a value, which is a number. For example, “2/4” and “1/2” are different fractions, but has the same value. For any real number x, the set of fractions whose values are less than x is RE.

F

The union of any two deterministic context-free languages must be a DCFL.

F

The intersection of any two deterministic context-free languages must be a DCFL.

F

The complement of any DCFL must be a DCFL.

T

Every DCFL is generated by an LR grammar.

T

The membership problem for a DCFL is in the class P-time.

T

If h : Σ₁ → Σ^*₂ is a function, L1 ∈ Σ^*₁ , L2 ⊆ Σ^*₂ , h(L1) = L2 and L1 is regular, then L2 must be regular.

T

If h : Σ₁ → Σ^*₂ is a function, L1 ∈ Σ^*₁ , L2 ⊆ Σ^*₂ , h(L1) = L2 and L1 is regular, then L1 must be regular.

F

If h : Σ₁ → Σ^*₂ is a function, L1 ∈ Σ^*₁ , L2 ⊆ Σ^*₂ , L1 = h −1 (L2) and L2 is regular then L1 must be regular.

T

If a computable sequence of fractions converges to x, then x must be a recursive real number.

F

If L is a recursively enumerable language, there must be a computable reduction of L to the halting problem.

F

If two context-free grammars are equivalent, there is must be a proof that they are equivalent.

F

If two context-free grammars are not equivalent, there is must be a proof that they are not equivalent.

T

The membership problem for any regular language is N C.

T

Given any sequence M1, . . . Mn of square Boolean matrices, the product M1 × M2 × · · · × Mn is N C computable.

T

The problem of determining whether a given integer is a square is N C.

T

The set of all real numbers which are limits of convergent sequences of fractions is countable

F

√ 2 is a recursive real number.

T

Let x be a real number whose decimal digits are all either 0 or 1. then x must be a recursive real number.

F

Every context-sensitive language is decidable.

T

P–time = EXP–time.

F