What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For example in this syntax:

$L = \{ww^R\mid w \in \Sigma^{\ast} \}$


1 Answer 1


Reverse. So for example $(001)^{R} = 100$. Or to overdo it, for an string $s = s_{1}s_{2}\ldots s_{n}$, the reverse $s^{R}$ is $s_{n}s_{n-1}\ldots s_{2}s_{1}$.

  • $\begingroup$ Is R defined for infinite length string? $\endgroup$
    – PleaseHelp
    Aug 6, 2015 at 8:18
  • 1
    $\begingroup$ @AtulGangwar while I can't say that it hasn't been done, it isn't possible in at least the naïve way as there's no character you can define as the "last" character to take as the first in the reversed string. I suppose you could imagine (this is speculative on my part) a set-up more like $\mathbb{R}$, where you could have closed intervals of strings that contain an infinite number of characters with a defined ordering, then it might work, but the computational model that this would map do would be very different to what we normally work with. $\endgroup$ Aug 7, 2015 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.