L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.

L = { <M,s> : s ∈ L(M) and |L(M)| % 2 = 0}. Prove that L ∉ D by a reduction from H.

One possible proof:

R(<M,w>) = 1. Define M#(x): 1.a If x = a then accept 1.b Save x 1.c Replace x with w on the input tape 1.d Run M on w 1.e Restore x 1.f If x = b accept 2. Return <M#,a>

If there were an Oracle Mₒ that could decide L, then C = Mₒ(R(<M,w>)) = Mₒ(<M#,a>) could decide H:

<M,w> ∈ H: M# would accept a at 1.a, proceed through 1.d, and then accept b at 1.f. Thus L(M#) = {a,b}, and Mₒ accepts <M#,a> because a ∈ {a,b}, and |{a,b}| %2 = 0.

<M,w> ∉ H: M# would accept a at 1.a, and loop forever at 1.d. Thus L(M#) = {a}, and Mₒ rejects <M#,a> because |{a}|%2 = 1.

But no TM could decide H, so Mₒ could not possibly exist.