On Two Letters versus Three
Dexter C. Kozen · 2002
If A is a context-free language over a two-letter alphabet, then the set of all words obtained by sorting words in A and the set of all permutations of words in A are context-free. This is false over alphabets of three or more letters. Thus these problems illustrate a difference in behavior between twoand three-letter alphabets. The following problem appeared on a recent exam at Cornell: Let be a finite alphabet with a fixed total ordering on the letters. For a string x 2, let sort x be the string obtained by sorting the letters in increasing order. For example, if a < b < c, then sort abacbaa = aaaabbc. ForA, let sortA = fsortx j x 2 Ag. Of the following three statements, two are false and one is true. Give counterexamples for the two false ones and a proof of the true one. (i) If A is regular, then so is sort A. (ii) If A is context-free, then so is sort A. (iii) If A is context-sensitive, then so is sort A. One might also ask the same questions about perm A, the set of all permutations of words in A. Of course, it is (i) and (ii) that are false, since sort (abc) = perm (abc) \\ a b c = fa n b n c n j n 0g: 1 Interestingly, (ii) is true for both sort and perm over a two-letter alphabet. This is quite surprising: whereas a two-letter alphabet is exponentially more succinct than a one-letter alphabet, one does not normally think of a break in behavior between two- and three-letter alphabets. In many applications, three letters (or for that matter any fixed finite number of letters) can be coded into two with only a linear loss of efficiency. Not so, apparently, in this case. In this short note we give an elementary proof of these facts. The proof for sort is a fairly straightforward construction relying on Parikh’s theorem and Pilling normal form, but the proof for perm is somewhat more involved, requiring a bit of linear algebra over integer lattices. Let =fa 1�::: �adg, and let: ! N d be the Parikh map (x) def