Recursive structure of MOS scales: Difference between revisions
| Line 413: | Line 413: | ||
# w₂(L, s) = the first K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) (which must be longer than w₁(L, s), since W₂ had more λ's than W₁) | # w₂(L, s) = the first K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) (which must be longer than w₁(L, s), since W₂ had more λ's than W₁) | ||
# w₃(L, s) = the last K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) | # w₃(L, s) = the last K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) | ||
Note that the latter two words have at most k s's. | Note that the latter two words have at most k s's, and that W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) has k chunks in total. | ||
If w₂ contains fewer complete chunks (<L...Ls preceded by where < is the left chunk boundary) or at least 2 more than w₃, we are done, since they must automatically have different numbers of s's. It suffices to consider the case where | If w₂ contains fewer complete chunks (<L...Ls preceded by where < is the left chunk boundary) or at least 2 more than w₃, we are done, since they must automatically have different numbers of s's. It suffices to consider the case where the intersection w₂ ∩ w₃ contains at least k-1 complete chunks, since otherwise W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) would have at least k+1 chunks, which would contradict the length of W₂(λ, σ). | ||
Hence it suffices to consider the following two cases, each split into subcases: | Hence it suffices to consider the following two cases, each split into subcases: | ||
Case 1 | '''Case 1''' | ||
Suppose w₂ and w₃ (which have the same length) contain the same number of complete chunks. | Suppose w₂ and w₃ (which have the same length) contain the same number of complete chunks. Then w₂ ∩ w₃ must contain at most k-2 complete chunks, giving the above contradiction. | ||
Case | '''Case 2''' | ||
If w₂ has one more complete chunk than w₃: | |||
(Below X denotes a chunk boundary, < > are chunk boundaries that are also the boundary of the word, [] are non-chunk-boundary word boundaries.) | |||
Case 2.1: | Case 2.1: | ||