1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You just specified it, though perhaps you should use different notation (invent one). $\endgroup$ – Yuval Filmus May 27 '14 at 23:37
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby May 27 '14 at 23:42
  • $\begingroup$ How do you define your inverse if $|\Sigma| > 2$? $\endgroup$ – Raphael May 28 '14 at 6:19
  • $\begingroup$ @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, ...)?" $\endgroup$ – Rick Decker May 28 '14 at 13:51
2
$\begingroup$

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.)

$\endgroup$

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.