Existe um método para provar a não regularidade das transformações de string?

Existem vários modelos diferentes para definir transformações entre idiomas. Transdutores de estado finito e transformações de gráficos definíveis pelo MSO sobre gráficos de cadeias de caracteres são as duas com as quais estou melhor familiarizado. Sabemos que os transdutores de estado finito bidirecional (que são mais expressivos que seus equivalentes unidirecionais) e as transformações de cadeia definíveis pelo MSO capturam o mesmo conjunto de transformações, juntamente com outros modelos menos conhecidos que usam combinadores. Essa classe de transformações é considerada regular e, portanto, é fácil mostrar que uma transformação é regular se você puder fornecer uma descrição dela com um desses modelos.

Existe uma maneira direta de dizer que uma transformação está fora dessa classe? Algo semelhante ao lema de bombeamento para linguagens regulares ou o teorema de Myhill-Nerode, mas para transformações de strings é o tipo de coisa que estou procurando.

Sua pergunta não está totalmente bem definida: como você recebe a transformação com a qual começa? Por exemplo, se você assumir que a transformação é dada por, por exemplo, uma máquina de Turing, claramente não há uma maneira algorítmica de decidir se é uma transdução regular.

No entanto, parece que você está perguntando se existe alguma caracterização "independente da máquina" das transduções de cadeia de caracteres (por exemplo, Myhill-Nerode).

Embora eu não conheça essa caracterização em geral (tenho certeza de que essa caracterização não é conhecida), existe uma caracterização para transdutores de strings com informações de origem, desenvolvidos por Bojnaczyk.

Você pode começar aqui.