CS 456 Final Exam (T/F/O & fill & Mult.Choice)

Every subset of a regular language is regular.

False

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.

False

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

True

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

False

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

True

The language {a^n b^n c^n : n is prime} is decidable.

True

If a language L is EXP-space complete, L must be decidable.

True

NC = P

Open

P = NP

Open

EXP-time = P-time

False

The Boolean Circuit Problem is NC

Open

3-SAT is P-time.

Open

Addition of binary numerals is NC.

True

Every language generated by a general grammar is recursive.

False

Every language generated by a general grammar is recursively enumerable.

True

The problem of whether two given context-free grammars are equivalent is co-RE.

True

The language of all fractions (using base 10 numeration) whose values are less than π is decidable. (Recall that a fraction is a string consisting of two numerals separated by a slash, "/".)

True

If L is RE and co-RE, then L is decidable.

True

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

False

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

True

If a Boolean expression is satisfiable, there is a P-time proof that it's satisfiable.

True

Every subset of any enumerable set is enumerable.

True

Every subset of any recursively enumerable set is recursively enumerable.

False

The binary numeral factorization problem is co-NP.

True

All C++ programs which halt with no input.

A Known to be N C.

B Known to be P–time, but not known to be N C.

C Known to be N P, but not known to be P–time and not known to be N P–complete.

D Known to be N P–complete.

E Known to be P–space but not known to be N P

F Known to be EXP–time but not nown to be P–space.

G Known to be EXP–space but not nown to be EXP–time.

H Known to be decidable, but not nown to be EXP–space.

K RE but not decidable.

L co-RE but not decidable.

M Neither RE nor co-RE.

(k) RE but not decidable.

All base 10 numerals for perfect squares.

A Known to be N C.

B Known to be P–time, but not known to be N C.

C Known to be N P, but not known to be P–time and not known to be N P–complete.

D Known to be N P–complete.

E Known to be P–space but not known to be N P

F Known to be decidable, but not known to be P–space.

G RE but not decidable.

H co-RE but not decidable.

I Neither RE nor co-RE.

(a) Known to be NC.

All context-free grammars that generate the Dyck language.

A Known to be N C.

B Known to be P–time, but not known to be N C.

C Known to be N P, but not known to be P–time and not known to be N P–complete.

D Known to be N P–complete.

E Known to be P–space but not known to be N P

F Known to be EXP–time but not nown to be P–space.

G Known to be EXP–space but not nown to be EXP–time.

H Known to be decidable, but not nown to be EXP–space.

K RE but not decidable.

L co-RE but not decidable.

M Neither RE nor co-RE.

(L) co-RE but not decidable.

All configurations of RUSH HOUR from which it's possible to win.

Known to be N C.

B Known to be P–time, but not known to be N C.

C Known to be N P, but not known to be P–time and not known to be N P–complete.

D Known to be N P–complete.

E Known to be P–space but not known to be N P

F Known to be EXP–time but not nown to be P–space.

G Known to be EXP–space but not nown to be EXP–time.

H Known to be decidable, but not nown to be EXP–space.

K RE but not decidable.

L co-RE but not decidable.

M Neither RE nor co-RE.

(E) Known to be P-space but not known to be NP

All satisfiable Boolean expressions.
A Known to be N C.

B Known to be P–time, but not known to be N C.

C Known to be N P, but not known to be P–time and not known to be N P–complete.

D Known to be N P–complete.

E Known to be P–space but not known to be N P

F Known to be decidable, but not known to be P–space.

G RE but not decidable.

H co-RE but not decidable.

K Neither RE nor co-RE

(D) Known to be NP-complete.

All binary numerals for composite integers. (Composite means not prime.)

A Known to be N C.

B Known to be P–time, but not known to be N C.

C Known to be N P, but not known to be P–time and not known to be N P–complete.

D Known to be N P–complete.

E Known to be P–space but not known to be N P

F Known to be EXP–time but not nown to be P–space.

G Known to be EXP–space but not nown to be EXP–time.

H Known to be decidable, but not nown to be EXP–space.

K RE but not decidable.

L co-RE but not decidable.

M Neither RE nor co-RE.

(B) Known to be P-time, but not known to be NC.

Define 'Accept' (That is, what does it mean for a machine M to accept a language L over an alphabet Σ.)

If M is given an input string w∈Σ∗, it will halt and accept w if and only if w∈L.

Define 'Decide' (That is, what does it mean for a machine M to decide a language L over an alphabet Σ.)

If M is given an input string w∈Σ∗, it will halt. If w∈L, M will accept w, if not, it will reject w.

Define 'Canonical order of a language L'

In the canonical order, if u,v ∈ L, we say u < v if either |u| < |v|, or |u| = |v| and u comes before
v in alphabetic ordering.

Which class of languages does each of these machine classes accept?
Deterministic finite automata.

Regular languages.

Which class of languages does each of these machine classes accept?
Non-Deterministic finite automata.

Regular languages.

Which class of languages does each of these machine classes accept?
Push-down automata.

Context-free languages.

Which class of languages does each of these machine classes accept?
Turing Machines.

Recursively enumerable languages.

--------- Spring 2022 below

------

There is some PDA that accepts 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.

False

The language {a^n b^n | n ≥ 0} is context-free.

True

The language {a^n b^n c^n | n ≥ 0} is context-free.

False

The language {a^i b^j c^k | j = i + k} is context-free.

True.

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

True

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

True

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

True

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

False

The language {a^n b^n c^n | n ≥ 0} is in the class P-time.

True

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

Open

The intersection of any two undecidable languages is undecidable.

False

Every NP language is decidable.

True

The intersection of two NP languages must be NP.

True

There exists a P-time algorithm which finds a maximum independent set in any graph G.

Open

NP = P-space

Open

EXP-space = P-space.

False

The traveling salesman problem (TSP) is NP-complete.

True

The knapsack problem is NP-complete.

True

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

True

The Boolean Circuit Problem is in P-time.

True

2-SAT is P-time.

True

Primality, using binary numerals, is P-time.

True

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

False

Every context-free language is in P.

True

Every context-free language is in NC.

True

Every language generated by an unrestricted grammar is recursive.

False

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

False

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

True

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.

True

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(2^(2^n) ).

False

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

True

Every bounded function is recursive.

False

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

Open

Every language is enumerable.

True

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

False

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

True

Rush Hour, the puzzle sold in game stores everywhere, generalized to a board of arbitrary size,
is NP-complete.

Open

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

Open

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

True

The computer language Pascal has Turing power.

True

The binary integer factorization problem is co-NP.

True

Label each of the following sets as countable or uncountable.
The set of integers.

countable

Label each of the following sets as countable or uncountable.
The set of rational numbers.

countable

Label each of the following sets as countable or uncountable.
The set of real numbers.

uncountable

Label each of the following sets as countable or uncountable.
The set of binary languages.

uncountable

Label each of the following sets as countable or uncountable.
The set of co-RE binary languages.

countable

Label each of the following sets as countable or uncountable.
The set of undecidable binary languages.

uncountable

Label each of the following sets as countable or uncountable.
The set of functions from integers to integers.

uncountable

Label each of the following sets as countable or uncountable.
The set of recursive real numbers.

countable

------ Fall 2022 below

-----

The intersection of any two N P languages is N P.

True

The independent set problem is P-time

True

If S is a recursive set of positive integers, then ∑_
n∈S 2^−n must be a recursive real number.

True

Multiplication of matrices with binary numeral entries is N C.

True

Equivalence of regular expressions is decidable.

True

Every recursively enumerable language is generated by a general grammar.

True

Equivalence of context-free grammars is co-RE.

True

The language consisting of all fractions whose values are less than the natural logarithm of 5.0
is recursive.

True

Every sliding block problem is P-space.

True

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

True

There is a polynomial time algorithm for checking whether an integer is prime.

True

Every finite language is regular.

NO ANSWER ON STUDY GUIDE but True...probably