# operate infinite times over a regular language

Let $$T:Σ^*\to Σ^*$$ be an operation such that $$T(L)$$ is regular for all regular languages $$L \in Σ^*$$.

Is it possible to prove $$T^∞(L)$$ is regular?

$$T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$$

• "Tread carefully on infinity", said someone. The beast of infinity is beyond our finite imagination. How do you define $T^\infty(L)$? For example, $\Sigma={a}$, $L=\Sigma^*$ and $T(a)=aa$. For another example, $\Sigma=\{a,b\}$, $L=\{a\}^*$, $T(a)=b$ and $T(b)=a$. I could think of several (or maybe infinitely many?) definitions. – John L. Feb 2 '19 at 3:50
• can I add a constraint eg: L⊆T(L), does this make it more reasonable? – DoYouLikeMiiii Feb 2 '19 at 3:58
• It looks like you want $T^\infty(L) =\cap_{i=1}^\infty T^n(L)$. Can you add that to the question? However, the dust is not settled down yet. – John L. Feb 2 '19 at 4:04
• is this problem unsolvable yet? – DoYouLikeMiiii Feb 2 '19 at 4:11
• Solvable. The answer is negative. Here is a counterexample. $T(\{a^{i}\})=\{a^{2i}\}$. We can see that $T^\infty(\{a\})$ is not regular. – John L. Feb 2 '19 at 4:12

Colleague Apass Jack already warned about the dangers of infinity, and he also indicated a very simple example that shows that a very simple iteration leads to a non-regular language. Case closed, but I like to add an observation: iterating simple local substitutions lead to Turing power, not just non-regularity.

The single steps of a Turing machine van be encoded, and performed with a regular operation. The instruction "on reading $$a$$ in state $$q$$, write $$b$$, move left and change to state $$p$$" is coded as rule $$aq \mapsto pb$$ and is extended to longer strings containing a single state as $$\alpha aq \beta \mapsto \alpha pb\beta$$. This operation can be extended to sets of instructions, and will map a regular language into a regular language. However,iterating them will actually generated Turing machine computations!

(I have an answer somewhere with this observation, but cannot find it.)