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.
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
Both these constructions will generate the other one.
To create a 6 step loop, we need
They generate the other one in that order.