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?


  • 2
    $\begingroup$ "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. $\endgroup$ – Apass.Jack Feb 2 at 3:50
  • $\begingroup$ can I add a constraint eg: L⊆T(L), does this make it more reasonable? $\endgroup$ – DoYouLikeMiiii Feb 2 at 3:58
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Feb 2 at 4:04
  • $\begingroup$ is this problem unsolvable yet? $\endgroup$ – DoYouLikeMiiii Feb 2 at 4:11
  • 2
    $\begingroup$ Solvable. The answer is negative. Here is a counterexample. $T(\{a^{i}\})=\{a^{2i}\}$. We can see that $T^\infty(\{a\})$ is not regular. $\endgroup$ – Apass.Jack Feb 2 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.)


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.