1Find a turing machine that recognizes the set of strings of

1.Find a turing machine that recognizes the set of strings of 0s and 1s containing at least one 1

Solution

C = {hM, Ri | M is a DFA and R is a regular expression with L(M) = L(R) }. Recall that the proof of Theorem 4.5 defines a Turing machine F that decides the language EQDFA = { hA, Bi | A and B are DFAs and L(A) = L(B) }. Then the following Turing machine T decides C: T = “On input hM, Ri, where M is a DFA and R is a regular expression: 1. Convert R into a DFA DR using the algorithm in the proof of Kleene’s Theorem. 2. Run TM decider F from Theorem 4.5 on input hM, DRi. 3. If F accepts, accept. If F rejects, reject.”