I'm about to study a system that takes words in a formal language $L$ and converts them into words in a different formal language $L'$. In other words: a formal language transformer. I was wondering if there is literature on formal language transformers, some standard way of studying, and defining them?

All I found are a 1995 paper by Cousot & Cousot on program analysis where formal language transformers are mentioned, but not really studied, and a 2005 presentation by Jaeho Shin that mentions the Cousot & Cousot paper. But maybe I'm looking in the wrong place or maybe I'm using the wrong vocabulary?

After all the effort in defining and studying the very many kinds of formal languages, it seems strange to me that nobody has bothered studying their transformations into each other.


Without knowing what kind of transformation you compute, it's unlikely that there's a useful word. Assuming that any two inputs are processed independently of each other, you're looking at (computable) function(al)s from $A^* \to B^*$ with two alphabets $A$ and $B$.

Here are some specific kinds of transformations:

| cite | improve this answer | |

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.