Recursive structure of MOS scales: Difference between revisions
No edit summary |
|||
| Line 46: | Line 46: | ||
Suppose there is a generator after chunking. Assume also that there are more L's than s's, and that the imperfect generator is larger than the perfect generator. This means that this interval, built on the chunk boundaries after expanding, will still be "a generator" on the chunk boundaries: it will be the same size on all but one of the chunk boundaries. Take one of the "perfect" (smaller) intervals. We showed previously that, before expansion, the step to its right was an L, just like its first step; therefore we can scoot it over for the entirety of the first chunk and keep it perfect. We now come to another chunk. If a "perfect" interval can be built on it then we can repeat. If the interval is imperfect, then we know that the step to its right is an s, which will make it smaller and thus perfect, and we can keep doing this for the remainder of the chunk. Therefore, the interval is a generator after expansion as well, since it is only imperfect in one position. | Suppose there is a generator after chunking. Assume also that there are more L's than s's, and that the imperfect generator is larger than the perfect generator. This means that this interval, built on the chunk boundaries after expanding, will still be "a generator" on the chunk boundaries: it will be the same size on all but one of the chunk boundaries. Take one of the "perfect" (smaller) intervals. We showed previously that, before expansion, the step to its right was an L, just like its first step; therefore we can scoot it over for the entirety of the first chunk and keep it perfect. We now come to another chunk. If a "perfect" interval can be built on it then we can repeat. If the interval is imperfect, then we know that the step to its right is an s, which will make it smaller and thus perfect, and we can keep doing this for the remainder of the chunk. Therefore, the interval is a generator after expansion as well, since it is only imperfect in one position. | ||
== Uniqueness and existence of generator== | == Uniqueness and existence of the generator== | ||
===Proof=== | ===Proof=== | ||
Every MOS can be reduced to nL 1s (or 1L ns). Each step of the reduction decreases either the number of L's or the number of s's (or both), so one of them must reach 1 at some point. ''(note that reducing further gets us to 1L 0s, which has a period, but no generator per se)'' | Every MOS can be reduced to nL 1s (or 1L ns). Each step of the reduction decreases either the number of L's or the number of s's (or both), so one of them must reach 1 at some point. ''(note that reducing further gets us to 1L 0s, which has a period, but no generator per se)'' | ||