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.