(a) D counts consecutive 0’s. Any ‘1’ resets the counter to s₀. s₄ is a trap (both transitions stay in s₄).

• s₂ accepts: the string ends with a run of exactly 2 consecutive 0’s (preceded by a 1 or start of string).
• s₄ accepts: the string contains a run of 4+ consecutive 0’s anywhere (once you hit s₄, you never leave).

L(D) = strings over {0,1} that either end with a block of exactly two consecutive 0’s (not preceded/followed by more 0’s) or contain a block of four or more consecutive 0’s.

More precisely: L(D) = {w ∈ {0,1}* | w ends in a run of exactly 2 consecutive 0’s, or w contains a run of ≥ 4 consecutive 0’s}.

(b) L(D′) = strings with an even number of 0’s. (r₀ = even count, r₁ = odd count. 1’s don’t change state.)

Product construction D′′ = (Q′′, {0, 1}, δ′′, (s₀, r₀), F′′) where F′′ = {s₂, s₄} × {r₀} = {(s₂, r₀), (s₄, r₀)}.

Exploring reachable states from (s₀, r₀):

10 reachable states (all 5 × 2 = 10 states are reachable). L(D′′) = strings from L(D) that also have an even number of 0’s.

Yes, SNFAs recognize exactly the regular languages.

Direction 1: Regular ⊆ SNFA. Every regular language has a DFA. A DFA has exactly one computation path for every input (determinism means one transition per state per symbol). If the DFA accepts, that is exactly 1 accepting path. If it rejects, that is 0 accepting paths. So every DFA is automatically a valid SNFA for the same language. Since every regular language has a DFA, every regular language is recognized by some SNFA. □

Direction 2: SNFA ⊆ Regular. Let N be an SNFA with states Q = {q₁, …, q_n} and accept states F. Build a DFA D that tracks, for each NFA state q_i, how many computation paths reach it: “0”, “1”, or “≥2”. Formally, the DFA state space is {0, 1, 2+}ⁿ, which is finite (3ⁿ states).

Transitions: On reading symbol a in DFA state (c₁, …, c_n), compute the new count for each q_j by summing the counts c_i over all q_i with q_j ∈ δ(q_i, a), capping at 2+.

Acceptance: D accepts iff the total number of accepting paths equals exactly 1. Formally: sum the counts for all states in F, and accept iff that sum equals 1.

This is a finite-state construction, so L(N) is regular. □

We need to match: anything, then ‘a’, then anything, then ‘b’, then anything, then ‘c’, then anything. Let Σ = (a | b | c).

The first and last Σ* can be omitted if you only care about containing the subsequence (they handle characters before the first ‘a’ and after the last ‘c’). But including them is cleaner and unambiguously correct. A shorter equivalent: (b | c)*a(a | b | c)*b(a | b | c)*c(a | b | c)* — the prefix only needs b’s and c’s since we pick the first ‘a’.

Yes, the proof can be completed.

Since |xy| ≤ p and w begins with a^p, the entire prefix xy lies in the a-block. So y = a^k for some 1 ≤ k ≤ p.

Pump with i = (p!/k) + 1:

xyⁱz = a^{p − k + k · i}b^p+p! = a^{p − k + k(p!/k + 1)}b^p+p! = a^{p + p!}b^p+p!

Now the number of a’s equals the number of b’s (both p + p!), so xyⁱz ∉ L. This contradicts the pumping lemma. □

Why p! is essential: We need the pumping exponent i = (p!/k) + 1 to be a non-negative integer, which requires k | p!. Since 1 ≤ k ≤ p, we know k divides p! (every integer from 1 to p divides p!). This is why we use p! and not a simpler offset.

Why a^pb^p+1 fails: With w = a^pb^p+1, pumping gives a^p−k+kib^p+1. For this to equal a^p+1b^p+1 (equal counts), we need ki − k = 1, i.e., k(i − 1) = 1, i.e., k = 1 and i = 2. But k could be 2, 3, …, p, and for those values no integer i makes k(i−1) = 1. We need to find a single i that works for all possible k, and a^pb^p+1 does not allow this.

(a) Assign each symbol a “weight”: a = +1, b = −2. Then L = strings with total weight 0.

Each non-ε rule must add one b (−2) and two a’s (+2) to maintain balance, but symbols can appear in any order:

S → ε | SS | aaSb | abSa | bSaa

Verification: S → SS allows concatenation of balanced strings (balanced + balanced = balanced). The three 3-symbol rules cover all orderings of (a, a, b) with S interspersed to allow arbitrary balanced strings between them. Every string with #_a = 2 · #_b can be built this way. 5 rules total. □

(b) PDA for L′ = { aⁱb^j | i ≠ j }.

Strategy: nondeterministically guess i < j or i > j at the start.

Branch 1 (i > j): Push all a’s onto the stack. Pop one per b. After all b’s, check the stack is nonempty → accept.

Branch 2 (i < j): Push all a’s onto the stack. Pop one per b. Once the stack is empty, read at least one more b → accept.

States: q₀ (start), q₁ (branch: i > j, pushing a’s), q₂ (branch: i > j, popping with b’s), q₃ (branch: i < j, pushing a’s), q₄ (branch: i < j, popping with b’s), q₅ (branch: i < j, reading extra b’s), q_acc.

Transitions:

• q₀ ⟶ ε, ε → $ ⟶ q₁  (guess i > j, push bottom marker)
• q₀ ⟶ ε, ε → $ ⟶ q₃  (guess i < j, push bottom marker)
• q₁: a, ε → A  (push a’s)
• q₁ ⟶ ε, ε → ε ⟶ q₂  (switch to reading b’s)
• q₂: b, A → ε  (pop one A per b)
• q₂ ⟶ ε, A → ε ⟶ q_acc  (stack still has A’s after b’s done ⇒ i > j ✓)
• q₃: a, ε → A  (push a’s)
• q₃ ⟶ ε, ε → ε ⟶ q₄  (switch to reading b’s)
• q₄: b, A → ε  (pop one A per b)
• q₄: b, $ → $ ⟶ q₅  (stack empty, still reading b ⇒ more b’s than a’s)
• q₅: b, $ → $  (read remaining b’s)
• q₅ ⟶ ε, $ → ε ⟶ q_acc  (accept)

7 states: {q₀, q₁, q₂, q₃, q₄, q₅, q_acc}. □

Note: The i > j branch accepts when, after reading all b’s (no more input), the stack still has at least one A. The nondeterministic ε-transition from q₂ to q_acc checks that A is on top (not $). The i < j branch accepts when the stack hits $ while b’s remain.

(a) Testing short words:

w = ε: q₀ reads ⊔ → q_acc. Accepts! But wait — ε has length 0. Is there a non-trivial accepted word?

Actually, ε is accepted: q₀ reads blank → accept. So ε is the shortest.

But let’s check if the question intends non-empty words. The shortest non-empty accepted word:

w = “0”:

q₀ 0 ⊔
⊢ X q₁ ⊔  (write X, move R, go to q₁)
⊢ q₂ X ⊔  (read ⊔, move L, go to q₂)
⊢ X q_rej ⊔  (read X in q₂ → reject)

Rejected. (After marking the first 0 with X and scanning right, q₂ finds X immediately — only one symbol was between the marks.)

w = “00”:

q₀ 00 ⊔
⊢ X q₁ 0 ⊔  (mark first 0)
⊢ X0 q₁ ⊔  (scan right past 0)
⊢ X q₂ 0 ⊔  (hit blank, move L)
⊢ q₃ X ⊔ ⊔  (erase the 0, write ⊔, move L)
⊢ X q₀ ⊔ ⊔  (read X in q₃, move R to q₀)
⊢ X ⊔ q_acc  (read ⊔ in q₀ → accept!)

“00” is accepted. Shortest non-empty word: “00” (length 2).

Technically ε is the shortest, but the question asks to “find the shortest word” and “show configurations”, so “00” gives a more instructive trace. Full credit for either answer with correct configurations.

(b) M’s algorithm: mark the leftmost unmarked 0 with X (reject if it sees a 1), scan right to the end of the input, erase the rightmost symbol (reject if it immediately sees X, meaning nothing was between mark and end), scan left back to X, then repeat from q₀ which skips over X’s. Accept when only X’s and blanks remain.

Each pass consumes one symbol from the left (must be 0) and one symbol from the right (can be 0 or 1). The process continues until nothing remains between the X markers.

This means:

• The string must start with 0 (first symbol read by q₀ after skipping X’s).
• The string must have even length (each pass removes exactly 2 symbols).
• All “left-half” symbols must be 0 (each pass requires a 0 on the left).

L(M) = { 0ⁿw | w ∈ {0, 1}ⁿ, n ≥ 0 } = strings of even length whose first half is all 0’s.

Equivalently: L(M) = {ε} ∪ { 0ⁿw | n ≥ 1, w ∈ {0, 1}ⁿ }.

Yes, L(M) is decidable. M always halts: each pass erases 2 symbols, strictly reducing the input, so M terminates in at most |w|/2 passes. Moreover, L(M) is a regular language (a DFA can track position and verify the first half is all 0’s by counting), so it is decidable.

(a) L_* is co-Turing-recognizable.

We show L_* is Turing-recognizable. Build TM R:

R = “On input ⟨M₁, M₂⟩:

1. Dovetail over all strings s ∈ Σ* and all step counts t = 1, 2, 3, …:
2. For each s and t:
   • Run M₁ on s for t steps. Record whether M₁ accepts/rejects/hasn’t halted.
   • For every way to partition s into k substrings s = w₁w₂…w_k (for all k ≥ 0): run M₂ on each w_i for t steps. If all w_i are accepted by M₂, then s ∈ L(M₂)*.
3. If we discover a witness s where the membership disagrees — either M₁ accepts s but no partition has all parts accepted by M₂ (within t steps), or some partition has all parts accepted by M₂ but M₁ rejects s — then accept (the pair is NOT in L_*).”

If L(M₁) ≠ L(M₂)*, some witness s exists and will eventually be found by dovetailing. So R recognizes L_*, which means L_* is co-TR. □

(b) L_* is undecidable.

Reduction: A_TM ≤_m L_*.

On input ⟨M, w⟩, construct:

• M₂ = “On input x: Accept if x = a. Reject otherwise.”  So L(M₂) = {a}, and L(M₂)* = a* = {ε, a, aa, aaa, …}.
• M₁ = “On input x: If x ∉ a*, reject. If x = ε, accept. Otherwise, run M on w. If M accepts, accept. Else reject.”

Analysis:

• M accepts w: M₁ accepts all of a* (x ∉ a* → reject, x = ε → accept, x = aⁿ with n ≥ 1 → M accepts w → accept). So L(M₁) = a* = L(M₂)*, thus ⟨M₁, M₂⟩ ∈ L_*.
• M does not accept w: M₁ only accepts ε (x ∉ a* → reject, x = ε → accept, x = aⁿ with n ≥ 1 → M doesn’t accept → reject/loop). So L(M₁) = {ε} ≠ a* = L(M₂)*, thus ⟨M₁, M₂⟩ ∉ L_*.

So ⟨M, w⟩ ∈ A_TM ⇔ f(⟨M, w⟩) ∈ L_*. The function f is computable. Thus A_TM ≤_m L_*.

Since A_TM is undecidable, L_* is undecidable. □

(c) L_* is not Turing-recognizable.

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

Therefore L_* is not Turing-recognizable. □

(a) No, ⟨M_ATM⟩ ∉ L_DEC.

M_ATM recognizes A_TM, so L(M_ATM) = A_TM. Since A_TM is undecidable, L(M_ATM) is not decidable, so ⟨M_ATM⟩ ∉ L_DEC.

(b) Yes, the student is correct that this reduction fails.

The reduction maps every input ⟨M, w⟩ to some ⟨M′⟩ ∈ L_DEC regardless of whether M accepts w (in both cases, L(M′) is decidable — either Σ* or ∅). A valid many-one reduction requires: ⟨M, w⟩ ∈ A_TM ⇔ f(⟨M, w⟩) ∈ L_DEC. Since both branches map into L_DEC, the “only if” direction fails.

Why a simple A_TM reduction fails: L_DEC is a “higher-order” property. The standard trick of building M′ whose language is either Σ* or ∅ doesn’t help because both Σ* and ∅ are decidable. To get a “no” instance of L_DEC, you need M′ to have an undecidable language — but that requires encoding a much more complex TM.

Conclusion: L_DEC IS undecidable (this follows from Rice’s theorem since “L(M) is decidable” is a non-trivial semantic property of TMs — some TMs have it, some don’t). But proving it requires a more sophisticated reduction than the simple A_TM approach above. In fact, L_DEC is Σ₃-complete in the arithmetic hierarchy, meaning it is “harder” than A_TM — no mapping reduction from A_TM to L_DEC or to L_DEC exists.

(a) SCHEDULE ∈ NP.

Certificate: a permutation σ of the tasks (the proposed ordering).

Verifier:

1. Compute the completion time of each task in order σ: C(σ(i)) = ∑_j=1ⁱ p(σ(j)).  (O(n))
2. Count how many tasks have C(σ(i)) > d(σ(i)).  (O(n))
3. Accept if the count is ≤ k.  (O(1))

All steps polynomial in input size. □

(b) 3SAT yes-instance.

U = {x, y, z}, C = {(x ∨ y ∨ ¬z), (¬x ∨ z ∨ y)}.

Satisfying assignment: x = T, y = T, z = T. First clause: T ∨ T ∨ F = T ✓. Second clause: F ∨ T ∨ T = T ✓.

(c) Apply the reduction.

n = 3 variables, m = 2 clauses. Tasks:

k = 0. Total tasks: 8 (processing time sum = 8).

(d) Is it a yes-instance?

No. There are 8 tasks, each with p = 1, so total processing time = 8. The last task finishes at time 8 regardless of ordering. But consider: for each variable u_i, both t_i and f_i have deadline 2i. With k = 0, both tasks must finish by time 2i. However, we have 2 tasks per variable, and tasks before u_i’s pair consume time too.

For variable u₁: t₁ and f₁ both have deadline 2. We can schedule at most 2 tasks by time 2. That works if t₁ and f₁ go first.

For variable u₂: t₂ and f₂ have deadline 4. By time 4 we can schedule 4 tasks. With t₁,f₁,t₂,f₂ first, all meet deadlines.

For variable u₃: deadline 6. By time 6 we schedule 6 tasks, all 6 variable tasks fit.

Then c₁ at time 7 (deadline 7 ✓) and c₂ at time 8 (deadline 8 ✓).

So actually yes — ordering [t₁, f₁, t₂, f₂, t₃, f₃, c₁, c₂] has all tasks meeting deadlines with k = 0. ✓

(e) The flaw.

The reduction always produces a yes-instance of SCHEDULE, even when the 3SAT instance is unsatisfiable. The problem is that k = 0 with these deadlines allows all variable tasks (both “true” and “false”) to be scheduled on time — the deadlines are loose enough to fit everything. The reduction does not encode the constraint that setting a variable to true should “conflict” with setting it to false.

Fix: Change the deadlines so that for each variable pair (t_i, f_i), only one of the two can meet its deadline. For example, set d(t_i) = d(f_i) = 2i − 1 (giving a “slot” of size 1 for two tasks). Then exactly one misses, and set k = n (one missed task per variable). The clause tasks must then be scheduled using the “slack” created by the satisfying assignment to also meet their deadlines.

(a) FALSE.

This is impossible. If L is TR and L is also TR, then L is decidable. Proof: let R₁ recognize L and R₂ recognize L. Build decider D: “On input w, run R₁ and R₂ in parallel (interleaving steps). If R₁ accepts, accept. If R₂ accepts, reject.” One of them must accept (w is either in L or in L), so D always halts. This is a theorem, not an assumption: L is decidable iff both L and L are TR.

(b) TRUE.

If L ∈ NP, there exists a polynomial-time verifier V and a polynomial q(n) bounding the certificate length. A brute-force algorithm: for input w of length n, enumerate all 2^q(n) possible certificates c and run V(w, c) on each. V runs in time poly(n), so total time is 2^q(n) · poly(n). This is bounded by 2^p(n) for a slightly larger polynomial p(n) = q(n) + O(log n). So L ∈ TIME(2^p(n)). □

This shows every NP language is solvable in (at worst) exponential time. The converse — whether EXPTIME contains languages outside NP — is a major open question (but we assume NP ≠ EXP).

(c) TRUE.

Counterexample: L = Σ* (regular), L′ = {aⁿbⁿ | n ≥ 0} (not regular). Then L ∪ L′ = Σ* which is regular. More interestingly: L = {aⁿb^m | n ≠ m} (not regular — wait, let’s pick valid examples). L = Σ* works. The union of any language with Σ* is Σ*, which is regular.

(d) FALSE.

E_TM = {⟨M⟩ | L(M) = ∅} is co-Turing-recognizable but not Turing-recognizable. A_TM is Turing-recognizable. If E_TM ≤_m A_TM, then since A_TM is TR, E_TM would be TR (mapping reductions preserve TR: if L ≤_m L′ and L′ is TR, then L is TR). But E_TM is not TR. Contradiction.

Note: the converse direction E_TM ≤_m A_TM IS true (both are TR), but that’s a different statement. E_TM itself sits outside the TR class.