1
$\begingroup$

I hope you can help me with this excersise:

Lets have finite sequence of characters $0$ and $1$. We are doing following algorithm:
If the sequence starts with $0$, we add $00$ to the end.
If the sequence starts with $1$, we add $1101$ to the end.
Then we remove first three characters.

Prove, that if the sequence repeats in cycles, the cycles are of even length.

Proof:
We are changing the length of the sequence, doing $n$ steps, by $n$. To get to the starting state of the loop, the length has to be changed doing $n$ steps, by $-n$. The total number of steps is $2n$, which is even.

We assume, that if $n = n+1$, the number of steps is still even.
We are changing the length of the sequence, doing $n+1$ steps, by $n+1$. To get to the starting state of the loop, the length has to be changed doing $n+1$ steps, by $-(n+1)$. The total number of steps is $2n + 2$, which is even.

Here are some examples:

In order to create a $2$-step loop, we need a sequence starting which some time comes to state $0xx1xx$ or $1xx0x$.
Both these constructions will generate the other one.

To create a $6$-step loop, we need
$1xx1xx1xx0xx0$ or
$1xx1xx0xx0xx0x$ or
$1xx0xx0xx0xx1xx$ or
$0xx0xx0xx1xx1xx1$ or
$0xx0xx1xx1xx1xx$ or
$0xx1xx1xx1xx0x$.
They generate the other one in that order.

  • 0
    Your argument is not very clear in my opinion. For one thing, if you "assume $n=n+1$", then you are assuming that $0=1$ and you can prove anything you want. This is really rather simple: if the cycle is length $n$, then after $n$ steps the total change in length must be $0$. If you apply the first rule (which decreases the total length by $1$) $k$ times, and you apply the second rule (which *increases* the total length by $1$) $\ell$ times, with $n=k+\ell$ being the number of steps in the cycle, then the length changes by $\ell-k$. And since the total change must be $0$...2010-12-06

1 Answers 1

2

Assuming you are talking about the sequence of bitstrings repeating in cycles, and the period of that,

Hint: You either increase the length of the bitstring by 1 or reduce it by 1.

  • 0
    @Ondrej: I don't think it is a valid proof yet. Perhaps you should explicitly mention the number of operations which increase the length (when first bit is 1) and the number of operations which decrease the length (when first bit is 0) and then show that the total is even. btw, Welcome :-)2010-12-06