What is word reversal $w^R$?

109 Views Asked by At

In the following context, what is the formal meaning of "reversal of word $w$"?

The free monoid on $A$ is the syntactic monoid of the language $\{ ww^R\ |\ w \in A^*\}$, where $w^R$ denotes the reversal of word $w$.

2

There are 2 best solutions below

3
On BEST ANSWER

Formally, elements of $A^*$ are finite sequences of $A$, that is, functions $\{1,2,\dots,n\}\to A$ for some $n\in\Bbb N$. Then, if $w=(a_1,\dots,a_{n})$ then we define $$w^R:= (a_n,\dots,a_1):=i\mapsto a_{n+1-i}$$

0
On

If $w=a_1a_2\cdots a_n$, then $w^R=a_na_{n-1}\cdots a_2a_1$