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.

  • 1
    *which* sequence repeats? The sequence you start with, the sequence of actions you take, the sequence you end up with, or the sequence of *finite sequences* that you obtain from the process?2010-12-06
  • 0
    It is always the same sequence, and the length of the cycle is the number of steps after it returns to its previous state (not necessarily starting state). E.g. starting sequence 10000 -> 10100 -> 001101 ->10100 -> 001101 -> ... and so on. Here the length of cycle is 2. I found that the length is typically 2 or 6.2010-12-06
  • 1
    Just a nit because you could start with 10100, but shouldn't 10000 to to 001101?2010-12-06
  • 0
    You are correct, i made a mistake, it should be 10000 -> 001101 -> 10100 -> 001101...2010-12-06
  • 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