1. Construct a state machine of a TM to decide {w ? {0, 1} * : w has at least tw

Question

1. Construct a state machine of a TM to decide {w ? {0, 1} * : w has at least two more occurrences of 1 than occurrences of 0}.

2. Write a low-level description of a TM to decide {w ? {0, 1} *: w is of the form xy where x, y are palindromes}.

3. Write a high-level description of a TM {w#x : w, x ? {0, 1} * , as binary integers w ? x, and there is a prime number y such that w ? y ? x}

4.  Suppose that we have a system specification that is written as a DFA S. We can feed in a string and then S will tell us whether or not the string is possible within the specification. But to build a system that actually does something useful, we also build a DFA D (over the same alphabet as S). We want to make sure that D satisfies the specification S; i.e., all of the behavior that D describes is allowed within the specification.

a• Produce an algorithm that, on input two DFAs D, S, says whether or not D satisfies the specification S. (Formalize it as a language first! Then construct a decider.)

b• Call the DFA D above completely abiding if D’s functionality exactly matches that of S; there is no behavior that S describes that D does not. Formalize this problem as a language, and give a decider that, on input two DFAs D, S to determine if D is completely abiding. (Hint: use your algorithm for part (a))

c• Deduce from your part (b) algorithm, if we were not going to use this algorithm, how many strings are needed to be tested to see if D is completely abiding. You can suppose that the alphabet for all DFAs involved is {0, 1}. (hint: columbæ offeret)

5. You are given two NFAs N1, N2 over the same alphabet, with n1, n2 states respectively. Give a procedure to construct an NFA N such that L(N) = L(N1) ? L(N2) using no more than n1 × n2 states. Note: you cannot simply convert the NFAs to DFAs, and apply the product construction since there may be too many states! Show that your procedure is correct.

Explanation / Answer

Let's prove that the Turing machine M above decides the language L1 intersection L2. M accepts w iff both M1 and M2 accept w iff w belongs to L1 AND w belongs to L2 iff w belongs to L1 intersection L2. M rejects w iff either M1 or M2 or both reject w iff w doesn't belong to L1 and/or w doesn't belong to L2 iff w doesn't belong to L1 intersection L2. Note that the machine M is guaranteed to halt, since M1 and M2 are deciders and so guaranteed to halt on all inputs.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.