¿Existe algún método para probar la no regularidad de las transformaciones de cadenas?

Existen varios modelos diferentes para definir transformaciones entre idiomas. Los transductores de estado finito y las transformaciones de gráficos definibles por MSO sobre gráficos de cadenas son los dos que mejor conozco. Sabemos que los transductores de estado finito de 2 vías (que son más expresivos que sus contrapartes de 1 vía) y las transformaciones de cadena definibles por MSO capturan el mismo conjunto de transformaciones junto con algunos otros modelos menos conocidos que usan combinadores. Esta clase de transformaciones se considera regular, por lo que es fácil mostrar que una transformación es regular si puede proporcionar una descripción de la misma con uno de estos modelos.

¿Hay una manera directa de decir que una transformación está fuera de esta clase? Algo similar al lema de bombeo para los idiomas regulares o el teorema de Myhill-Nerode, pero para las transformaciones de cadenas es el tipo de cosa que estoy buscando.

Su pregunta no está del todo bien definida: ¿cómo se le da la transformación con la que comienza? Por ejemplo, si supone que la transformación está dada, por ejemplo, por una máquina de Turing, entonces claramente no hay una forma algorítmica de decidir si se trata de una transducción regular.

Sin embargo, parece que lo que está preguntando es si existe alguna caracterización "independiente de la máquina" de las transducciones de cadenas (por ejemplo, Myhill-Nerode).

Si bien no conozco tal caracterización en general (estoy bastante seguro de que no se conoce dicha caracterización), existe tal caracterización para los transductores de cadena con información de origen, desarrollada por Bojnaczyk.

Puedes comenzar aquí.