x1x2 xk10 x1x2 xk101 3 Note that there are four types

x₁x₂ . . . x_k?10 ? x₁x₂ . . . x_k?101 (3)

Note that there are four types of transitions: (1) Take a string ending in 1 and add a 0, (2) take a string ending in 0 and add a 0, (3) take a string ending in 0 and add a 1, (4) take a string and add its reversal to the beginning (turning it into a palindrome).

a. Prove that the string 10011001 is reachable from the initial string 0.

b. Prove that the string 0110110 is not reachable from the initial string 0.

c. Prove that a reachable string can never contain three consecutive 1

Solution

a)

10011001 can be constructed in the following steps:

0

01 (rule 2)

1001 (rule 4)

10011001 (rule 4)

b)

0110110 cannot be constructed by the steps given because:

Note that 0110110 has odd length. So the last step is not rule 4, since rule 4 will always create an even sized palindrome. Hence only possible last move is 011011 -> 0110110 by rule 1.

Now we examine whether 011011 is constructible?

Note that 011011 is not a palindrome and hence we are again forced to assume that the last move in construction of 011011 was not rule 4. Hence, only possible last step in constructrion of 011011 is

01101 -> 011011

This is not a given rule and hence this step can\'t be carried out. So 011011 cant be made, and hence 0110111 cant be made.

c)

Suppose that while the construction of a string, we have constructed k digits and so far, we donot have any 3 consecutive 1s.

x1x2x3...xk has no 3 consecutive 1s.

Now applying rule 1,2, or 3 will not create three consecutive 1s as every rule has atleast one 0 in it.

So, the only hope of taking a step which introduces 3 consecutive 1s is rule 4.

Note that rule 4 would give

xkk(k-1).....x2x1x1x2.....xk

Now xkk(k-1).....x2x1 as well as x1x2...xk wont have any 3 consecutive 1s.

So, only possibility of having 3 1s is at the center where they join.

ie. if and only if x2x1x1x2 = 1111

Can we construct a string with the first 2 digits as 1?

When we start, first digit is 0, and hence if we end up with a string x1x2...xk where x1=1 and x2=1,

it can only happen if we applied rule 4 to some string y1y2...11 and the it trasformed into 11...y2y1y1y2....11.

But since there is no production z1z2...zk1 -> z1z2...zk11 , such a string y1y2...11 with both the ending digits =1 cant be made (similar to what we showed in part b)

Hence we can never make a string x1x2...xk where x1=1 and x2=1.

Hence we when we apply rule 4 to x1x2.....xk, the middle part x2x1x1x2 will never be 1111, and hence we will never have 3 consecutive 1s.
Hence proved.