Ì Exam ple 0.1.21: The reverse of a string is defined by the recusive rules
a
a
wa
aw
R
R
R
=
=
,
( )
for all a
w
∈
∈
Σ
Σ
,
.
* Using this prove that
( )
uv
v u
R
R R
=
for all u v
, ∈
+
Σ .
Solu tion
Given that a
R = a,
( )
wa
aw
R
R
=
.
Now we have to prove ( )
.
uv
v u
R
R R
=
Let us assume that u = wb and v = wa.
LHS
uv
wbwa
bw aw
bw aw
bw aw
v
R
R
R
R
R
R
R
R
R
=
=
=
⋅
=
=
=
( )
(
)
(
)(
)
( ) ( )
⋅
=
u
RHS
R
Hence proved.
Ì Exam ple 0.1.22: Given Σ = { , }
a b obtain Σ
* .
(a) Give an example of a finite language in Σ.
(b) Given
{
}
L
a b n
n n
=
≥
:
0 , check if the strings aabb, aaaabbbb,
abb are in the language L.
Solu tion
Σ = { , }
a b
Therefore we have Σ
*
{ , , , , , , ,
, }
= λ a b aa ab ba bb aaa
(a) {a, aa, aab} is an example of a finite language in Σ.
(i) aa bb → a string in L. (n = 2)
(ii) aaaa bbbb → a string in L. (n = 4)
(iii) abb → not a string in L (since there is no n satisfying this).
Introduction
21