The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998

Detailed Solutions

Chapter 3, Problem 32

The trick here is mostly in figuring out a way to pace the submachine that will handle the substring z, since that substring is half the length of the input. The submachine for z must make only one transition for every two transitions made by the submachine for substring x, which dictates the pace (since it is fed the real input). One solution is to use a toggle: on even positions in x, the submachine for z makes a transition, but on odd ones it does not. Otherwise, the machine is constructed exactly along the lines discussed in class for this class of languages: a state of the NFA we are building will be a 7-tuple, augmented into an 8-tuple by the odd/even toggle. The 7-tuple members include 4 current states for the 4 submachines handling the 4 substrings and 3 markers that store the initial guesses for the starting positions of the 2nd, 3rd, and 4th submachines. (Note that the 1st and 3rd submachines must be kept separate: they have exactly the same transition function, but need not start in the same state and thus need separate current states.)

So, given a DFA M=(Sigma,Q,S,F,delta) for L, we construct an NFA M'=(Sigma,Q',S',F',delta') for L' as follows.

Q' = {S'} union {(q_i,q_j,q_k,q_l,q_m,q_n,q_o,t) | q_i,q_j,q_k,q_l,q_m,q_n,q_o in Q and in {odd,even}}

delta'(S',epsilon) = {(S,q_i,q_i,q_j,q_j,q_k,q_k,even) | q_i,q_j,q_k in Q}

delta'((q_i,q_j,q_k,q_l,q_m,q_n,q_o,even),a) = {(q_i',q_j,q_k',q_l,q_m',q_n,q_o,odd) | delta(q_i,a)=q_i', delta(q_m,a)=q_m', and there exist alpha and beta such that delta(delta(q_k,alpha),beta)=q_k'}

delta'((q_i,q_j,q_k,q_l,q_m,q_n,q_o,odd),a) = {(q_i',q_j,q_k',q_l,q_m',q_n,q_o',even) | delta(q_i,a)=q_i', delta(q_m,a)=q_m', there exist alpha and beta such that delta(delta(q_k,alpha),beta)=q_k', and there exists gamma such that delta(q_o,gamma)=q_o'}

F'={(q_i,q_i,q_j,q_j,q_k,q_k,q,even) | q_i,q_j,q_k in Q and q in F}

In order to accept, we must be in an "even" state, i.e., we must have seen an even number of input characters; the transition function keeps toggling between odd and even state labels and the submachine for z only makes transitions when we read an even-numbered input character.