# Formal language inverse

How can you specify the "inverse" of a word, so: let's say a word consists of a's and b's the language is: $ww^{-1}$ the second word is the same as the first but every a is replaced by b and every b by a

• You just specified it, though perhaps you should use different notation (invent one). – Yuval Filmus May 27 '14 at 23:37
• I'm not aware of any notation for that. Even if there is "standard" notation for it, it's not in common enough use that you can just use it without defining it. – David Richerby May 27 '14 at 23:42
• How do you define your inverse if $|\Sigma| > 2$? – Raphael May 28 '14 at 6:19
• @Raphael. One might define the "inverse" of a word $w$ to be the result of applying a permutation $\sigma$ on the alphabet to the characters of $w$. Then for a language $L$ we could define $\sigma(L)$ to be the language resulting from the application of $\sigma$ to the words in $L$, leading to questions like, "given a (regular, context-free, ...) language $L$, under what conditions is $\{w\sigma(w)\mid w\in L\}$ also (regular, CF, ...)?" – Rick Decker May 28 '14 at 13:51

What you're calling $w^{-1}$ is a special case of what's known as a homomorphism, where, informally speaking, we define a map $h$, from an alphabet $\Sigma$ to strings over an alphabet $\Gamma$ and then extend this in a natural way to maps of words. In your case, the map is particularly simple: $h(a)=b$ and $h(b)=a$. There's quite a bit known about such maps; for instance both regular and context-free languages are closed under homomorphisms.
(For what it's worth, your $ww^{-1}$ language isn't regular.)