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}*}.

CSC 520 HW #3 Spring 2020 1. (12.5 points). Derive a characteristic function for the TM in the diagram below. --------------------------------------------- | | v a a a | >Ra,☐ ----------Ra,☐---------->Ra,☐----------> | | | ☐| ☐| ☐| | | | | | | | | v ☐ | | Lb,☐----------> n | | | | | b| | | | | | v ☐ | | Lb,☐----------> n | | b | | |<------------------- v ☐ | Lb,☐-----> y | | v ☐ b| Lb,☐----------> n | | v | n b| | v ☐ Lb,☐----------> n | b| | v a,b L--------> n | ☐| | v y

2. (12.5 points) 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}*}. As examples, which must not appear in your proof: Let L(M₁) = {b,aa}. Then <M₁,b> ∈ L because b ∈ L(M₁) and a ∉ L(M₁); <M₁,aa> ∉ L because both aa and b are in L(M₁); and <M₁,a> ∉ L because a ∉ L(M₁). Prove that L ∉ D using a reduction from H. Do not Rice's theorem.