Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-12-16
Computer Science
Formal Languages and Automata Theory
revision correcting some typos
Scientific paper
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. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that the operation diag, which extracts the diagonal of words of square length arranged in a square array, preserves regularity but does not preserve context-freeness.
Mousavi Hamoon
Shallit Jeffrey
No associations
LandOfFree
Filtrations of Formal Languages by Arithmetic Progressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Filtrations of Formal Languages by Arithmetic Progressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Filtrations of Formal Languages by Arithmetic Progressions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136612