(a) L(D) = the set of all strings over {a, b} that do not contain "aa" as a substring.

Reasoning: q₀ is the only accept state. Reading one ‘a’ goes to q₁ (not accepting — need to “return” via b). Reading two consecutive a’s goes to q₂, which is a trap (all transitions go to q₂, never accepting). So D accepts iff the input never has two a’s in a row.

(b) L(D′) = strings with an even number of a’s (p₀ counts even, p₁ counts odd; b’s don’t change state).

Product construction D′′ = (Q′′, {a, b}, δ′′, (q₀, p₀), F′′) where F′′ = F × F′ = {(q₀, p₀)}.

Starting from (q₀, p₀), explore reachable states:

6 reachable states. L(D′′) = strings with no “aa” AND an even number of a’s.

Start state: {q₀}. Build all reachable subsets:

3 reachable states. A DFA state is accepting if it contains q₂.

L(N) = strings over {0, 1} that contain the substring “01” — reading a 0 “loads” q₁, and then a 1 reaches q₂.

We need: (1) at least one ‘a’ somewhere, and (2) the last character is ‘b’.

Strategy: get to the first ‘a’ (skip b’s), then anything, then end with ‘b’.

Equivalent shorter forms: b*a(a | b)*b. The first (a | b)* also works — it already subsumes b*.

Yes, the proof can be completed.

Since |xy| ≤ p and w starts with a^p, the prefix xy lies entirely within the a-block. So y = a^k for some k ≥ 1.

Pump with i = 2:

xy²z = a^p+kb^p

Since k ≥ 1, we have p + k > p, so the number of a’s exceeds the number of b’s.

Therefore xy²z ∉ L, contradicting the pumping lemma.

(a) We show that w = “ab” has two distinct leftmost derivations.

Derivation 1:

S ⇒ XX ⇒ aXbX ⇒ abX ⇒ ab

(Expand left X → aXb, then X → ε, then right X → ε.)

Derivation 2:

S ⇒ XX ⇒ X ⇒ aXb ⇒ ab

(Expand left X → ε, then remaining X → aXb, then X → ε.)

Two different leftmost derivations for “ab”, so G is ambiguous. □

(b) PDA for L = { aⁿb^m | n ≥ 0, m ≥ 1 }:

3 states suffice: q₀ (start), q₁ (reading b’s), q_acc (accept).

Transitions:

• q₀ ⟶ ε, ε → $ ⟶ q₀  (push start marker — or just initialize with $ on stack)
• q₀: a, ε → ε  (read a’s, no stack needed)
• q₀: b, ε → ε  → q₁  (read first b, move to q₁)
• q₁: b, ε → ε  (read more b’s)
• q₁: ε, ε → ε  → q_acc  (accept when done)

Since we don’t need to match counts, the stack is not used for counting. We only need to ensure at least one b is read, which the state structure handles.

(a) w = “aab”.

Configurations (underlined = head position):

q₀ aab
⊢ a q₁ ab
⊢ aa q₁ b
⊢ aab q_acc

M accepts “aab”. ✓

(b) Yes, L(M) is decidable.

L(M) = { aⁿb | n ≥ 1 } — strings of one or more a’s followed by exactly one b.

Two arguments:

1. M always halts: every transition moves right, and the tape is finite, so M must eventually read ⊔ and halt (accept or reject). Since M is a decider, L(M) is decidable.
2. L(M) is regular (recognized by a simple DFA), and every regular language is decidable.

(a) L_ε is Turing-recognizable.

Build TM R = “On input ⟨M⟩:

1. Simulate M on input ε.
2. If M accepts, accept.”

If ⟨M⟩ ∈ L_ε, then M accepts ε, so R accepts. If M does not accept ε (rejects or loops), R either rejects or loops — which is fine for a recognizer. So R recognizes L_ε. □

(b) L_ε is undecidable.

Reduction: A_TM ≤_m L_ε.

Assume for contradiction that some TM D decides L_ε. Build TM S that decides A_TM:

S = “On input ⟨M, w⟩:

1. Construct TM M′ = “On input x:
    (a) Ignore x.
    (b) Run M on w.
    (c) If M accepts w, accept.”
2. Run D on ⟨M′⟩.
3. If D accepts, accept. If D rejects, reject.”

Correctness:

• If M accepts w: then M′ accepts every input (including ε), so ε ∈ L(M′), so ⟨M′⟩ ∈ L_ε, so D accepts, so S accepts.
• If M does not accept w: then M′ accepts nothing, so ε ∉ L(M′), so ⟨M′⟩ ∉ L_ε, so D rejects, so S rejects.

S decides A_TM. But A_TM is undecidable. Contradiction. □

(c) L_ε is not co-Turing-recognizable.

From (a), L_ε is TR. From (b), L_ε is undecidable.

If L_ε were also co-TR, then L_ε would be both TR and co-TR, which implies L_ε is decidable (a language is decidable iff both it and its complement are recognizable). But (b) shows L_ε is undecidable. Contradiction.

(a) M′ = “On input x:

1. Ignore x.
2. Run M on w.
3. If M accepts w, accept.”

Two cases:

• M accepts w ⇒ M′ accepts every input ⇒ L(M′) = Σ* ≠ ∅ ⇒ ⟨M′⟩ ∈ L_NE. ✓
• M does not accept w ⇒ M′ accepts nothing ⇒ L(M′) = ∅ ⇒ ⟨M′⟩ ∉ L_NE. ✓

So ⟨M, w⟩ ∈ A_TM ⇔ F(⟨M, w⟩) ∈ L_NE. The reduction is correct.

(b) The reduction A_TM ≤_m L_NE proves:

• Undecidable: A_TM is undecidable, so L_NE is undecidable.
• Not co-TR: The same computable function f witnesses A_TM ≤_m L_NE. Since A_TM is not TR, L_NE is not TR, which means L_NE is not co-TR.
• TR: L_NE is Turing-recognizable (dovetail: enumerate all strings x₁, x₂, … and simulate M on each; if M accepts any x_i, then L(M) ≠ ∅, so accept). This is not shown by the reduction itself, but is a separate argument.

(a) TEAM FORMATION ∈ NP.

Certificate: a subset T ⊆ P.

Verifier:

1. Check |T| ≤ t.  (O(|P|))
2. Compute S = ∪_{p ∈ T} skill(p).  (O(|P| · |K|))
3. Check S = K.  (O(|K|))

All steps polynomial in input size. □

(b) VERTEX COVER yes-instance.

V = {v₁, v₂, v₃, v₄}, E = {e₁={v₁,v₂}, e₂={v₂,v₃}, e₃={v₃,v₄}}, k = 2.

Cover: {v₂, v₃} — v₂ covers e₁, e₂ and v₃ covers e₂, e₃. All edges covered. ✓

(c) Apply the reduction.

• P = {v₁, v₂, v₃, v₄}
• skill(v₁) = {e₁}
• skill(v₂) = {e₁, e₂}
• skill(v₃) = {e₂, e₃}
• skill(v₄) = {e₃}
• K = {e₁, e₂, e₃}
• t = |V| − k = 4 − 2 = 2

(d) Yes-instance?

T = {v₂, v₃}, |T| = 2 ≤ 2 = t. skill(v₂) ∪ skill(v₃) = {e₁,e₂} ∪ {e₂,e₃} = {e₁,e₂,e₃} = K. ✓

Yes, it is a yes-instance of TEAM FORMATION.

(e) The flaw.

The reduction sets t = |V| − k, but it should be t = k. VERTEX COVER asks for a cover of size ≤ k, and the reduction maps vertices to players and edges to skills. A vertex cover of size k corresponds to a team of size k that covers all edges/skills. Using |V| − k inverts the bound.

Counterexample: Take the same graph with k = 1. The VC instance is a no-instance (can’t cover 3 edges with 1 vertex). But the reduction gives t = 4 − 1 = 3, and T = {v₁, v₂, v₃} covers all edges — so TEAM FORMATION says yes. The reduction maps No → Yes, which is incorrect.

(a) FALSE.

Counterexample: The language “the n-th symbol from the end is ‘a’” over {a, b} can be recognized by an NFA with n + 1 states (guess the position), but any equivalent DFA requires at least 2ⁿ states (subset construction can produce exponentially many reachable states).

More concretely: an NFA for “second-to-last symbol is ‘a’” needs 3 states; the minimal DFA needs 4 states.

(b) TRUE.

Proof: Every decider is also a recognizer. A decider for L halts on all inputs, accepting if w ∈ L and rejecting if w ∉ L. The accept behavior already satisfies the definition of a recognizer (accepts exactly the strings in L). Since decidable means “there exists a decider,” and every decider is a recognizer, decidable ⊆ Turing-recognizable. □

(c) FALSE.

Proof by pumping lemma: Suppose L = { aⁿbⁿ | n ≥ 0 } is regular. Let p be the pumping length. Take w = a^pb^p ∈ L. Then w = xyz with |xy| ≤ p, |y| ≥ 1, so y = a^k (k ≥ 1). Pumping: xy²z = a^p+kb^p ∉ L since p + k ≠ p. Contradiction. □

(d) FALSE.

Counterexample: A_TM ≤_m A_TM via the identity function (f(x) = x). A_TM is undecidable, but A_TM is Turing-recognizable.

The reduction A ≤_m B with A undecidable proves that B is undecidable, not that B is unrecognizable. Undecidable and not-TR are different properties.