A new pumping lemma for indexed languages, with an application to infinite words

作者：Smith Tim^*

来源：Information and Computation, 2017, 252: 176-186.

DOI：10.1016/j.ic.2016.11.002

• Infinite word
• Indexed language
• Prefix language
• Morphic word
• Pumping lemma

We prove a pumping lemma in order to characterize the infinite words determined by indexed languages. An infinite language L determines an infinite word alpha if every string in Lis a prefix of a. If Lis regular or context-free, it is known that alpha must be ultimately periodic. We show that if Lis an indexed language, then alpha is a morphic word, i.e., alpha can be generated by iterating a morphism under a coding. Since the other direction, that every morphic word is determined by some indexed language, also holds, this implies that the infinite words determined by indexed languages are exactly the morphic words. The pumping lemma which we use to obtain this result generalizes one recently proved for the class ETOL.

• 出版日期2017-2
• 单位东北大学