Hint for Homework 3, Problem 2

In this problem you should show that any DFA M = (Q,A,d,s,F) can be transformed into a (different) DFA (or NFA) M' = (Q',A,d',s',F') such that if the language recognized by M is L(M)=L, then M' recognizes L(M') = T(L), where T is the transformation described in the problem.

The hint is to set Q' = Q x {0,1} in the transformed automaton.

Similarly for the second part of the problem, this time using the language transformation I.