So here's a pretty simple problem that, on the surface, seems pretty complicated.
Imagine a string of 0's and 1's (call it 's') and the reverse of the string (call it 'r'). For instance
s = 1100
r = 0011
Now, interpret 's' as a base-2 value and interpret 'r' as a base-3 value.
s = 1100 (base-2 = 12)
r = 0011 (base-3 = 4)
If 's' is a string such that 's' is divisibly by 3 but 'r' is NOT divisible by 2, then we put 's' into a collection of strings and call that collection the language L.
In this case, 's' is not in L.
The problem is to determine whether or not any string 's' will be in L. If not, to prove it convincingly. If so, find the shortest string that is in L.
So that's the task you are being given here.
------------------------------------------------------------------------------------
For those interested in where this rather odd problem came from, read on.
I'm getting my lecture materials put together for this upcoming semester and have been trying to come up with interesting problems that are sufficiently simple that they can be solved by hand using the concepts of finite automata. In particular, I'm trying to come up with problems that involve the use of most of the concepts we are covering in order to solve (at least via a finite automaton).
For those not familiar with the term "finite automaton", it is essentially a super simple finite state machine. You have an input string of symbols and, on each clock cycle, you read one symbol and transition to the next state based only on your current state and the current input symbol. Each state outputs either a 0 or a 1. These are all suppressed by a global signal that enable the output once the string has been completely read as well as halting the machine. If the final output is a 1 then the machine "accepts" the input string otherwise it doesn't.
In playing around with a couple of ideas, I thought of strings that, when read in one direction and interpreted as being in one number base are divisible by one thing and, when read in the other direction and interpreted as being a number in a different number base, are divisible by something else. They idea is for the students to construct small machines that perform incremental parts of the task and then combined them.
Originally I wanted to have the problem be to find strings that were appropriately divisibly in both directions, but in trying to build up the equivalence classes, I noticed a pattern in that while all of the strings that were base-2 values divisible 3 were, when reversed, base-3 values divisible by 2, the converse was not true -- there were base-3 strings divisible by 2 for which the reversed strings were not base-2 strings divisible by 3. If this turned out to always be the case, then the language degenerates.
But then the idea hit me to incorporate a few other concepts. The first is taking the complement of a language, and the second is constructing a language to prove or disprove a hypothesis.
The hypothesis here is the following: Every binary value that is divisible by three will, if reversed and interpreted as a base-3 value, be divisibly by 2.
To prove that this hypothesis is wrong, it is sufficient to come up with a single value that violates the hypothesis. Any approach used to find that value is technically legitimate since the correctness of the counterexample can be proven directly from it. But to prove that the hypothesis is correct, you must provide a convincing mathematical argument that no such value exists.
It turns out that this problem, using finite automata, is actually quite easy to solve. In about twenty minutes I had constructed a machine that proved that such values DO exist and that could be used to generate them.
Think of the kind of program you would write in a high level language to do this -- and it would probably not be capable of proving that no values exists should that be the case. With that in mind, I find it somewhat remarkable that a six-state automaton is all that was needed and the pattern of values that are accepted is quite simple.
Even more powerfully, if it had turned out that no such values exist, then the machine would have had but a single state and that would have constituted a rigorous proof of the hypothesis.
Imagine a string of 0's and 1's (call it 's') and the reverse of the string (call it 'r'). For instance
s = 1100
r = 0011
Now, interpret 's' as a base-2 value and interpret 'r' as a base-3 value.
s = 1100 (base-2 = 12)
r = 0011 (base-3 = 4)
If 's' is a string such that 's' is divisibly by 3 but 'r' is NOT divisible by 2, then we put 's' into a collection of strings and call that collection the language L.
In this case, 's' is not in L.
The problem is to determine whether or not any string 's' will be in L. If not, to prove it convincingly. If so, find the shortest string that is in L.
So that's the task you are being given here.
------------------------------------------------------------------------------------
For those interested in where this rather odd problem came from, read on.
I'm getting my lecture materials put together for this upcoming semester and have been trying to come up with interesting problems that are sufficiently simple that they can be solved by hand using the concepts of finite automata. In particular, I'm trying to come up with problems that involve the use of most of the concepts we are covering in order to solve (at least via a finite automaton).
For those not familiar with the term "finite automaton", it is essentially a super simple finite state machine. You have an input string of symbols and, on each clock cycle, you read one symbol and transition to the next state based only on your current state and the current input symbol. Each state outputs either a 0 or a 1. These are all suppressed by a global signal that enable the output once the string has been completely read as well as halting the machine. If the final output is a 1 then the machine "accepts" the input string otherwise it doesn't.
In playing around with a couple of ideas, I thought of strings that, when read in one direction and interpreted as being in one number base are divisible by one thing and, when read in the other direction and interpreted as being a number in a different number base, are divisible by something else. They idea is for the students to construct small machines that perform incremental parts of the task and then combined them.
Originally I wanted to have the problem be to find strings that were appropriately divisibly in both directions, but in trying to build up the equivalence classes, I noticed a pattern in that while all of the strings that were base-2 values divisible 3 were, when reversed, base-3 values divisible by 2, the converse was not true -- there were base-3 strings divisible by 2 for which the reversed strings were not base-2 strings divisible by 3. If this turned out to always be the case, then the language degenerates.
But then the idea hit me to incorporate a few other concepts. The first is taking the complement of a language, and the second is constructing a language to prove or disprove a hypothesis.
The hypothesis here is the following: Every binary value that is divisible by three will, if reversed and interpreted as a base-3 value, be divisibly by 2.
To prove that this hypothesis is wrong, it is sufficient to come up with a single value that violates the hypothesis. Any approach used to find that value is technically legitimate since the correctness of the counterexample can be proven directly from it. But to prove that the hypothesis is correct, you must provide a convincing mathematical argument that no such value exists.
It turns out that this problem, using finite automata, is actually quite easy to solve. In about twenty minutes I had constructed a machine that proved that such values DO exist and that could be used to generate them.
Think of the kind of program you would write in a high level language to do this -- and it would probably not be capable of proving that no values exists should that be the case. With that in mind, I find it somewhat remarkable that a six-state automaton is all that was needed and the pattern of values that are accepted is quite simple.
Even more powerfully, if it had turned out that no such values exist, then the machine would have had but a single state and that would have constituted a rigorous proof of the hypothesis.