Definition:
Let
x
be a string over
S
.
The
reversal
of
x
,
reversal
(
x
)
, is defined as:
1)
if
x
=
e
then
reversal(
e
)
=
e
2)
if
x
=
a
1
…
a
n
then reversal(
a
1
…
a
n
) =
a
n
…
a
1
for some
n
³
1, and
a
i
Î
S
for all
i
= 1,…,
n
Example:
Consider
x
=1010
Task:
reversal(
x
)
reversal(
) =
,
so
a
1
a
1
a
2
a
2
a
3
a
3
a
4
a
4
reversal(
) =
1
1
0
0
1
1
0
0
Reversal of String
Gist:
reversal(
a
1
…
a
n
) =
a
n
…
a
1
7/20