0

Let us say that x is a set of binary numbers $$x = \{0, 1, 1001\}$$ Am I correct that $x^R$ is equal $$x^R = \{0,1,1001\}$$ or is it: $$x^R = \{1,0,0110\}$$ What I mean by that is: do we create a reversal for binary by a switch between zeros and ones, or do we do it by putting the whole set in diverted order?

J.-E. Pin
  • 40,163
Ariel Grabijas
  • 117
  • 2
    What is your source for this notation? I've never seen it before. – Patrick Stevens Feb 07 '16 at 21:17
  • The source is my university class "introduction to automata theory" (not in english), but there is not much about it there, thats why i try to find out more. You can find similar notation for context free grammars in automata theory when you use $L^R$ where $L$ is a language. – Ariel Grabijas Feb 07 '16 at 21:22
  • http://math.stackexchange.com/questions/1643815/parser-for-reversed-language – Ariel Grabijas Feb 07 '16 at 21:26

2 Answers2

1

The reversal of $1001$ is $1001$. (You could have chosen a better example!) $0110$ is the complement (or ones' complement) of $1001$.

TonyK
  • 64,559
  • Ok, so just to be clear for future generations. Acording to this, the reversal of $101000$ would be $000101$. Correct me if I am wrong. Thanks! – Ariel Grabijas Feb 07 '16 at 21:32
  • 2
    That's right. But you have to be careful! You are not dealing with binary numbers here, because (for instance) $1$ and $01$ represent the same number, but their reversals $1$ and $10$ don't. You are dealing with binary strings, which is different: $1$ and $01$ are not the same string. – TonyK Feb 07 '16 at 21:34
  • That's very fair point, I didnt look at this that way. And there can be really some errors made because of it. Thanks! – Ariel Grabijas Feb 07 '16 at 22:15
1

If $w = a_1a_2 \cdots a_n$ is a (binary) word, then $w^R = a_n \cdots a_2a_1$. If $L$ is a set of words, then $L^R = \{w^R \mid w \in L\}$. Therefore, $\{0,1,1001\}^R = \{0,1,1001\}$.

J.-E. Pin
  • 40,163