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. | |||
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. Hence it suffices to consider the following two cases, each split into subcases: | 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. Hence it suffices to consider the following two cases, each split into subcases: | ||
Line 421: | Line 422: | ||
Case 1.1: | Case 1.1: | ||
w2: <L ... sXL ... sXL ... sXL ... sXL ...] | w2: <L ... sXL ... sXL ... sXL ... sXL ...L] (complete chunks followed by one or more L's) | ||
w3: <L ... sXL ... sXL ... sXL ... s> | w3: <L ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
This implies that the last chunk is bigger than the first one, a contradiction because w₂ begins in λ. | This implies that the last chunk is bigger than the first one, a contradiction because w₂ begins in λ. | ||
Line 428: | Line 429: | ||
Case 1.2: | Case 1.2: | ||
w1: s[something with k s's] | w1: s[something with k s's] | ||
w2: <L ... sXL ... sXL ... sXL ... s> | w2: <L ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
w3: <L ... sXL ... sXL ... sXL ... s> | w3: <L ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
Truncate the strings as follows, to get three distinct K-steps in w: | Truncate the strings as follows, to get three distinct K-steps in w: | ||
Line 440: | Line 441: | ||
Case 1.3: | Case 1.3: | ||
w2: <L ... sXL ... sXL ... sXL ... sXL ...] | w2: <L ... sXL ... sXL ... sXL ... sXL ...L] (complete chunks followed by one or more L's) | ||
w3: [... sXL ... sXL ... sXL ... sXL ... s> | w3: [... sXL ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks) | ||
or | or | ||
Case 1.4: | Case 1.4: | ||
w2: <L ... sXL ... sXL ... sXL ... | w2: <L ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
w3: [... sXL ... sXL ... sXL ... sXL ... s> | w3: [... sXL ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks) | ||
(both 1.3 and 1.4 imply w₃ has one more s). | (both 1.3 and 1.4 imply w₃ has one more s). | ||
Line 456: | Line 457: | ||
Case 2.1: | Case 2.1: | ||
w2: <L ... sXL ... sXL ... sXL ... sXL ... s> | w2: <L ... sXL ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
w3: <L ... sXL ... sXL ... sXL ... s> | w3: <L ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
⇒ w₂ has | ⇒ w₂ has k s's and w₃ has (k-1) s's, contradicting the assumption that w is a mos. | ||
Case 2.2: | Case 2.2: | ||
w2: <L ... sXL ... sXL ... sXL ... sXL ... s> | w2: <L ... sXL ... sXL ... sXL ... sXL ... s> (complete chunks only) | ||
w3: [sXL ... sXL ... sXL ... sXL ... s> | w3: [sXL ... sXL ... sXL ... sXL ... s> (s followed by complete chunks) | ||
⇒ do the same trick as in Case 1.2 | ⇒ do the same trick as in Case 1.2 | ||
Case 2.3: | Case 2.3: | ||
w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...] | w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...] (complete chunks followed by one or more L's) | ||
w3: [ ... sXL ... sXL ... sXL ... sXL ... s> | w3: [ ... sXL ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks) | ||
Case 2.4: | Case 2.4: | ||
w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...] | w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...] (complete chunks followed by one or more L's) | ||
w3: <L ... sXL ... sXL ... sXL ... s> | w3: <L ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks) | ||
Both 2.3 and 2.4 are contradictions since the first chunk is λ so has to be at least as big as the last one. | Both 2.3 and 2.4 are contradictions since the first chunk is λ so has to be at least as big as the last one. |