Affiliations: School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada. hamoon.mousavihaji@uwaterloo.ca; shallit@cs.uwaterloo.ca
Note: [] Address for correspondence: School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada
Abstract: A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness.
