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} \}$


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 '15 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$ – Luke Mathieson Aug 7 '15 at 0:37

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.