DFA Encodings: Design a multi-tape Turing Machine that takes as input M,w = M#w for some M D(Q3) and w {a,b} and accepts iff w L(M).

For example, the accepted input could be,

$1&2&1&0&1&1 : 0 : 1&2#aabbaa

$1&2&1&0&1&1 : 0 : 1#aa

The following inputs are rejected:

$1&2&1&0&1&1 : 0 : 1&2#abaabbbab

$1&2&1&0&1&1 : 0 : #aa

The input $1&2&1&0&1&1 : 0 : #aa is rejected because there are no accepting states.