Part (a)

q₀ tracks "even number of a’s seen." The start state q₀ has seen zero a’s (even), so:

Part (b) — Product construction

Symmetric difference: accept when exactly one of D₁, D₂ accepts (XOR).

Product states: (q_i, p_j). Start: (q₀, p₀).

Accept states F = {(q_i, p_j) | exactly one of q_i ∈ F₁, p_j ∈ F₂}.

• (q₀, p₀): q₀ ∈ F₁ ✓, p₀ ∉ F₂ → exactly one → accept
• (q₀, p₁): q₀ ∈ F₁ ✓, p₁ ∈ F₂ ✓ → both → reject
• (q₁, p₀): q₁ ∉ F₁, p₀ ∉ F₂ → neither → reject
• (q₁, p₁): q₁ ∉ F₁, p₁ ∈ F₂ ✓ → exactly one → accept

Transition table:

All 4 states are reachable from the start state. L(D) = "even #a’s XOR odd #b’s."

Step 1 — Build GNFA

Add new start state q_s with ε-transition to q₀, and new accept state q_a with ε-transition from q₂.

GNFA transitions (before elimination):

• q_s → q₀: ε
• q₀ → q₀: 0
• q₀ → q₁: 1
• q₁ → q₁: 1
• q₁ → q₂: 0
• q₂ → q₂: 0
• q₂ → q₀: 1
• q₂ → q_a: ε

Step 2 — Eliminate q₁

For each pair (q_i, q_j) where q_i has an edge to q₁ and q₁ has an edge to q_j:

Formula: R(q_i, q_j) = R_old(q_i, q_j) ∪ R(q_i, q₁) · R(q₁, q₁)* · R(q₁, q_j)

• q₁’s self-loop: 1
• Into q₁: q₀ → q₁ via "1"
• Out of q₁: q₁ → q₂ via "0"

Only affected pair: (q₀, q₂)

Old q₀ → q₂: ∅ (no direct edge)

New q₀ → q₂: ∅ ∪ 1 · 1* · 0 = 1·1*·0 = 1⁺0

Resulting GNFA

States: {q_s, q₀, q₂, q_a}. Transitions:

The path through q₁ means: read one or more 1’s, then a 0 to reach q₂.

Key insight

The substring "110" is forbidden. After seeing "11", the next character cannot be 0 — it must be another 1 (or the string ends). So once a run of two or more 1’s starts, only more 1’s can follow until the string ends.

Building the regex

The string consists of two phases:

• Phase 1: Any sequence of "0" and "10" blocks — these can never create "110"
• Phase 2: A trailing run of 1’s (possibly empty) — once we start a run of ≥2 ones, we can’t go back to 0

Verification

The (0|10)* part ensures every 1 in phase 1 is immediately followed by 0 — so no two consecutive 1’s can occur before the final trailing block.

Setup

Assume for contradiction that L is regular with pumping length p.

Choose \(w = a^p b a^p\). Then \(w \in L\) since \(w^R = a^p b a^p = w\), and \(|w| = 2p + 1 \ge p\).

Pumping

By the pumping lemma, \(w = xyz\) where:

1. \(|xy| \le p\)
2. \(|y| \ge 1\)
3. \(xy^i z \in L\) for all \(i \ge 0\)

Since \(|xy| \le p\), both x and y lie entirely within the first block of a’s. So \(y = a^k\) for some \(k \ge 1\).

Pump down: i = 0

$$xy^0z = xz = a^{p-k} b a^p$$

Left side has \(p - k\) a’s before b. Right side has \(p\) a’s after b.

Since \(k \ge 1\), we have \(p - k < p\), so the string is not a palindrome.

Part (a) — Ambiguity

G is not ambiguous.

Every word in L(G) has the form \(wcw^R\) where \(w \in \{a,b\}^*\). The derivation is uniquely forced:

• The outermost symbols of the sentential form determine which rule applies
• If the string starts with a (and ends with a), we must use S → aSa
• If the string starts with b (and ends with b), we must use S → bSb
• If the remaining string is just "c", we must use S → c

Part (b) — PDA

Strategy: push symbols until c is read, then pop matching symbols.

States: q_start, q_push, q_pop, q_acc.

Understanding M

M operates in rounds. Each round:

1. q₀: Mark the leftmost a with X, go right
2. q₁: Scan right past all a’s to find the right end
3. q₂: Erase the rightmost a (replace with ␣), go left
4. q₃: Scan left past all a’s back to the X marker, restart

Each round removes a pair: one from the left (marked X) and one from the right (erased). Accepts when all a’s are consumed. Rejects if in q₂ no a is left (only X), meaning odd number of a’s.

Part (a) — w = aaaa

Part (b)

Part (a) — L is Turing-recognizable (2 pts)

Build a TM T that recognizes L using dovetailing:

T = “On input ⟨M⟩:

1. For n = 1, 2, 3, …
2.  Run M on strings s₁, s₂, …, s_n for n steps each
3.  Count the number of distinct strings accepted so far
4.  If the count exceeds n, accept.”

More precisely: for each threshold k = 1, 2, …, dovetail until k distinct strings are found to be accepted. If L(M) is infinite, every threshold k is eventually met, so T accepts. If L(M) is finite, T never reaches a high enough threshold and loops (never accepts).

Part (b) — L is undecidable (4 pts)

Reduce from A_TM = {⟨M, w⟩ | M accepts w}.

Assume for contradiction that decider R decides L. Build decider S for A_TM:

S = “On input ⟨M, w⟩:

1. Construct TM M′ = “On input x: ignore x. Run M on w. If M accepts w, accept.”
2. Run R on ⟨M′⟩.
3. If R accepts, accept. If R rejects, reject.”

Correctness:

• If M accepts w: M′ accepts every input → L(M′) = Σ* (infinite) → ⟨M′⟩ ∈ L → R accepts → S accepts.
• If M does not accept w: M′ accepts nothing → L(M′) = ∅ (finite) → ⟨M′⟩ ∉ L → R rejects → S rejects.

So S decides A_TM. Contradiction since A_TM is undecidable.

Part (c) — L is not co-TR (1 pt)

From (a), L is Turing-recognizable. If L were also co-Turing-recognizable, then L would be both TR and co-TR, which means L would be decidable (by running both recognizers in parallel). But (b) shows L is undecidable. Contradiction.

Part (a)

Correctness of the reduction

• M accepts w → M′ accepts all x with |x| ≤ 5 (step 2 always reaches step 3, which accepts) → ⟨M′⟩ ∈ L
• M does not accept w (rejects or loops) → M′ rejects or loops on all x with |x| ≤ 5 → M′ does not accept any string of length ≤ 5 → ⟨M′⟩ ∉ L

Part (b)

A_TM ≤_m L, so L is undecidable.

For the recognizability class: L is co-Turing-recognizable.

To see this, we build a recognizer for the complement \(\overline{L}\) = {⟨M⟩ | ∃ string x with |x| ≤ 5 that M does not accept}:

“On input ⟨M⟩: Run M on all strings of length 0, 1, …, 5 in parallel (dovetail). There are finitely many such strings. If any run halts and rejects, accept.”

This recognizes \(\overline{L}\), so L is co-TR.

Part (a) — COLORFUL MATCHING ∈ NP

Certificate: a set of edges M.

Verifier checks in polynomial time:

1. |M| ≥ m
2. M is a valid matching: no two edges in M share a vertex
3. All edges in M have distinct colors: no two edges in M have the same color

Part (b) — VC yes-instance

V = {v₁, v₂, v₃, v₄}, E = {(v₁,v₂), (v₂,v₃), (v₃,v₄), (v₁,v₃)}, K = 2.

Part (c) — Apply the reduction

Bipartite graph: Left side A = {v₁, v₂, v₃, v₄}, right side B = {e₁, e₂, e₃, e₄}.

Edges in the bipartite graph (vertex v connected to edge e iff v is an endpoint):

• v₁ — e₁ (v₁v₂), v₁ — e₄ (v₁v₃)
• v₂ — e₁ (v₁v₂), v₂ — e₂ (v₂v₃)
• v₃ — e₂ (v₂v₃), v₃ — e₃ (v₃v₄), v₃ — e₄ (v₁v₃)
• v₄ — e₃ (v₃v₄)

All bipartite edges are colored 1. m = K = 2.

Part (d)

Part (e) — The flaw and fix

Flaw: All edges are assigned the same color (color 1). This means the "colorful" constraint forbids any matching of size ≥ 2, regardless of the VC instance. The reduction always produces a no-instance (for K ≥ 2), so it cannot be correct.

Alternatively: drop the color constraint entirely, reducing to standard bipartite matching. But this changes the target problem, so it’s a weaker fix.

(a) True

Given recognizers T₁ for L₁ and T₂ for L₂, build recognizer T for L₁ ∩ L₂:

T = “On input w: Run T₁ and T₂ on w in parallel (dovetail). If both accept, accept.”

If w ∈ L₁ ∩ L₂: both eventually accept → T accepts. If w ∉ L₁ ∩ L₂: at least one never accepts → T never accepts.

(b) True

A DFA processes input in a single left-to-right pass, reading each symbol once. Running time is O(n) where n = |w|. Since O(n) ⊂ O(n^k) for k = 1, this is polynomial.

(c) True

A ≤_P B means there exists a poly-time computable function f such that x ∈ A iff f(x) ∈ B.

Since B ∈ NP, there is a poly-time verifier V_B for B.

Build verifier V_A for A: “On input (x, c): compute f(x) in poly time. Run V_B(f(x), c). Accept iff V_B accepts.”

Total time: poly(|x|) for f + poly(|f(x)|) for V_B = polynomial.

(d) True

Construct mapping f: on input ⟨M, w⟩, output ⟨M′, w⟩ where:

M′ = “On input x: simulate M on x. If M accepts, accept. If M rejects, loop forever.”

• M accepts w → M′ halts on w (accepts) → ⟨M′, w⟩ ∈ HALT_TM ✓
• M rejects w → M′ loops on w → ⟨M′, w⟩ ∉ HALT_TM ✓
• M loops on w → M′ loops on w → ⟨M′, w⟩ ∉ HALT_TM ✓