A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿbⁿ | n > 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L1 ∪ L2 where L1 = {w | w has even number of 1's} and L2 = {w | w contains 001 as a substring}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {0ⁿ1ⁿ | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) > n_b(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) ≠ n_b(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w | w has equal number of 0's and 1's}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^{n^2} | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^{2^n} | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿ | n = r + 2q, where r and q are both prime numbers}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿbⁿ | n ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^pb^q | p and q are prime numbers}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^{n^2}b^{m^2} | n, m ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) and n_b(w) both are prime numbers}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^n!b^m! | n, m ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^n! | n ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿb^j | n = j²}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿ | n is a prime number}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w | |w| is a multiple of three}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {<M, w> | M is a Turing machine that accepts a string w}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {<M, w> | M is a Turing machine that does not accept a string w}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿb^m | n, m ≥ 1, n ≠ m}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿbⁿcⁿ | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {0ⁿ1ⁿ | n ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁱb^jc^k | i = j or i = k, where i, j, k ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) = n_b(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) = n_b(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b, c}^∗ | n_a(w) + n_b(w) ≠ n_c(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^q | q is a prime number}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^n! | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^mbⁿ | m > n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b, c}^∗ | n_a(w) + n_b(w) = n_c(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b, c}^∗ | n_a(w) + n_b(w) > n_c(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w | w has an equal number of occurrences of a's and b's}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w | w has an equal number of occurrences of 01 and 10 as substrings}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

{aⁿba^mba^n+m | n, m ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^mbⁿ | m < n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) = n_b(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {ww^R | w ∈ {a, b}^∗}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿb²ⁿ | n ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {wcw^R | w ∈ {a, b}^∗}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿb^mc^n+m | n, m ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿb^m | n ≤ m ≤ 3n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿbⁿcⁿ | n ≥ 0}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {ww | w ∈ {0, 1}^∗}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁱb^jc^k | 0 ≤ i ≤ j ≤ k ≤ n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {ww | w ∈ {a, b}^∗}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^{2^n} | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^mbⁿ | m > n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^mbⁿ | m < n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^mbⁿ | m ≠ n}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b}^∗ | n_a(w) ≠ n_b(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {a^{n^2} | n ≥ 1}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁱb^jc^k | i · j = k}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {aⁿ | n is a prime number}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {P | P is a polynomial with an integral root}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b, c}^∗ | n_a(w) + n_b(w) > 2n_c(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {w ∈ {a, b, c}^∗ | n_a(w) + n_b(w) ≠ 2n_c(w)}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {<M, w> | M is a NFA that does not accept a string w}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {<M, w> | M is a non-deterministic PDA that does not accept a string w}

A. Regular language.

B. Context-free language but not regular language.

C. Turing-decidable language but not context-free language.

D. Turing-recognizable language but not Turing-decidable language.

E. language that is not Turing-recognizable

L = {<M, w> | M is a non-deterministic TM that does not accept a string w}

Is this language Turing-decideable?

A_DFA = {<B, w> | B is a DFA that accepts input string w}

Is this language Turing-decideable?

A_NFA = {<B, w> | B is a NFA that accepts input string w}

Is this language Turing-decideable?

A_REX = {<R, w> | R is a regular expression that generates input string w}

Is this language Turing-decideable?

A_CFG = {<G, w> | G is a CFG that generates input string w}

Is this language Turing-decideable?

HA_DFA = {<B, w> | B is a DFA that halts on input string w and reports accept or reject}

Is this language Turing-decideable?

HA_NFA = {<B, w> | B is a NFA that halts on input string w and reports accept or reject}

Is this language Turing-decideable?

A_REX = {<R, w> | R is a regular expression that generates input string w}

Is this language Turing-decideable?

HA_TM = {<M, w> | M is a TM that halts on input string w and reports accept or reject}

Is this language Turing-decideable?

A_CFG = {<G, w> | G is a CFG that generates input string w}

Is this language Turing-decideable?

Complement(A_TM), where A_TM = {<M, w> | M is a TM that accepts string w}

Is this language Turing-decideable?

E_DFA = {<A> | A is a DFA and L(A) = ∅}

Is this language Turing-decideable?

E_CFG = {<G> | G is a CFG and and L(G) = ∅}

Is this language Turing-decideable?

EQ_DFA = {<A, B> | A and B are DFAs and L(A) = L(B)}

Is this language Turing-decideable?

EQ_CFG = {<G1, G2> | G1 and G2 are context-free grammars and L(G1) = L(G2)}

Is this language Turing-decideable?

EQ_TM = {<A, B> | A and B are Turing machines and L(A) = L(B)}

Is this language Turing-decideable?

HALT_NFA = {<M, w> | M is an NFA that halts on input string w}

Is this language Turing-decideable?

HALT_TM = {<M, w> | M is a TM that halts on input string w}

Is this language Turing-decideable?

NE_DFA = {<A> | A is a DFA and L(A) ≠ ∅}

Is this language Turing-decideable?

NE_CFG = {<G> | G is a CFG and and L(G) ≠ ∅}

Is this language Turing-decideable?

NE_TM = {<M> | M is a TM and L(M) ≠ ∅}

Is this language Turing-decideable?

NEQ_DFA = {>A, B> | A and B are DFAs and L(A) ≠ L(B)}

Is this language Turing-decideable?

NEQ_CFG = {<G, H> | G and H are CFGs and L(G) ≠ L(H)}

Is this language Turing-decideable?

NEQ_TM = {<M₁, M₂> | M₁ and M₂ are TMs and L(M1) ≠ L(M2)}

Is this language Turing-decideable?

AMB_CFG = {G | G is a CFG and G is ambiguous}

It is true; since the set of languages that are recognized by a pushdown automata (deterministic or not), or Context-Free Languages, is a subset of the set of languages that are decidable by a Turing machine (deterministic or not), it follows automatically that L₂ ⊆ L₁.

(Note: DTM = NTM; whereas DPDA ⊂ NPDA.)

Justify that there exists a language that cannot be recognized by a Turing machine by proving the following two statements:

(i) The set of all Turing machines are countable.

(ii) The set of all languages over a given alphabet Σ is uncountable.

(i) The set of all Turing machines are countable.

Proof.

(From TEXTBOOK, Cor. 4.18) "The set of all Turing machines is countable because each Turing machine M has an encoding into a string <M>. If we simply omit those strings that are not legal encodings of Turing machines, we can obtain a list of all Turing machines."

The encoding of the TM's is as follow:

Let δ(q_i , x_j) = (q_k, x_l, y_m) ⇒ 10ⁱ10^j10^k10^l10^m1 (use 1's as delimiters); and let 10ⁱ10^j10^k10^l10^m be called "code-1", excluding the last 1-bit of the string; & etc; and "code-last" be the empty string.

Let, the encoding, be

<M> = 111"code-1"11"code-2"11...11"code-last"111

since <M> is a binary sequence with a fixed length (since M is represented with finite amount of information), so we can list all TM’s using the encoding stated above.

Therefore, the set of all Turing machines are countable.

(ii) The set of all languages over a given alphabet Σ is uncountable.

Proof.

The set of all strings over Σ is Σ^∗ = {s1, s2, ...}, which is countable.

The set of all languages over Σ would then be P = 2^Σ∗, the power set where each element of it is a combination of some of the strings from Σ^∗. Hence, we want to show that P is uncountable.

In order to do so, we would apply the characteristic sequence method onto P; i.e., χ(P), which has entries χi ∈ {0, 1}, indicating whether a string in Σ^∗ is being included in P at that corresponding location ∀i, with infinitely many such i’s. Therefore, χ(P) is the collection of all infinite binary sequences.

By Cor. 4.18, χ(P) is not countable; thus, the set of all languages over Σ is uncountable. 

Union: YYYY

Intersection: YNYY

Complementation: YNYN

Proof. (Class note, bottom of p. 48)

If P = NP, it is clear that every problem in NPC belongs to P. Now assume that there is a problem B ∈ NPC that can be solved in polynomial time deterministically. Then by definition of B ∈ NPC, any problem in NP can be transformed to B in polynomial time deterministically, which can then be solved in polynomial time deterministically using the algorithm for B. Hence, NP ⊆ P. Since P ⊆ NP, we conclude that P = NP, which completes the proof.

Let G be an arbitrary graph as an input to Hamiltonian Path (HP) problem.

We then construct a graph G' as an input to the Hamiltonian Cycle (HC ) problem as follow:

Given V(G) = {v₁, ..., v_n}, the vertex set, and E(G), the edge set; then, V(G') = V(G) ∪ {v₀}; and E(G') = E(G) ∪ {(v₀, v_i) | i = 1, ..., n};

i.e., in G' , add a new vertex v₀ that is connected to every vertex that is also in V(G). 

Claim: G has a HP iff G' has a HC.

Proof.

Suppose G has a HP starting with v_i and end with v_j, not necessarily the same vertex. Then, G' has a HC, namely (v₀, v_i, ..., v_j, v₀). Conversely, suppose G' has a HC with two edges (v₀, v_a) & (v_b , v₀) in the cycle. Then, G has a HP, namely (v_a, ..., v_b). Therefore, HP ≤_P HC; thus, HC problems are as hard as HP problems