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$ – John L. Feb 2 '19 at 3:50
  • $\begingroup$ can I add a constraint eg: L⊆T(L), does this make it more reasonable? $\endgroup$ – DoYouLikeMiiii Feb 2 '19 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$ – John L. Feb 2 '19 at 4:04
  • $\begingroup$ is this problem unsolvable yet? $\endgroup$ – DoYouLikeMiiii Feb 2 '19 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$ – 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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