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

In this paper, the author proves a pumping lemma in order to characterize the infinite words determined by indexed languages. A \textit{word} is a concatenation of symbols, called \textit{letters}, taken over a set called \textit{alphabet}. A (finite or infinite) set of words is called a \textit{language}. A \textit{prefix language} is a language \(L\) such that for all \(x,y \in L\), either \(x\) is a prefix of \(y\) or \(y\) is a prefix of \(x\). Every infinite prefix language determines a single infinite word \(\alpha\), in the sense that every word in \(L\) is a prefix of \(\alpha\). It is known that if a language \(L\) is regular or context-free, then the infinite word determined by \(L\) must be ultimately periodic. This result was first proved by \textit{R. V. Book} [Math. Syst. Theory 10, 229--237 (1977; Zbl 0358.68107)] using a pumping lemma for context-free languages. The class of \textit{indexed languages} consists of the languages generated by indexed grammars. In this kind of grammars, nonterminals are augmented with stacks which can be pushed, popped, and copied to other nonterminals as the derivation proceeds. This class falls between the classes of context-free languages and context-sensitive languages in the Chomsky hierarchy and includes all of the stack automata classes and rewriting systems classes whose infinite words were characterized by the same author in previous papers [Theor. Comput. Sci. 595, 1--10 (2015; Zbl 1328.68120); LIPICS -- Leibniz Int. Proc. Inform. 24, 413--424 (2013; Zbl 1359.68179)]. The author shows that if \(L\) is an indexed language, then the infinite word \(\alpha\) determined by \(L\) 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 infinite words determined by indexed languages are exactly the morphic words.