Question

please answer a,b, and c

Consider the following Turing Machine. M = “On input hA,Bi where A and B are DFAs: 1. Iterate through strings in Σ∗ in shortlex order; where Σ represents the common symbols of their input alphabets. For each string iterated, simulate both A and B on it. 2. If a string is ever encountered that both A and B accept, then accept.”

(a) (2 points) Give a description, in English, of the language that M recognizes.

(b) (2 points) Is M a decider? explain why or why not.

(c) (1 points) If we were to modify M so that in step 2. it rejects instead of accepts if A and B both accept a common string, what language would the resulting machine recognize?

Answer 1

a) M recognizes the language of dfa pairs which has atleast one common accepting string.

b) No M is not a decider,because if suppose a dfa pair x and y dont have any common string to accept,then the turing machine will never halt.

c) modified M recognizes the language of dfa pairs which does not have any common accepting string.