(b) To find L 2 L 2 , we concatenate words in L 2 with words in L 2 so that
{
}
L L
b b aba abab aba ba
2 2
4
2
2
2
=
,
,
,
Ì Exam ple 0.1.31: Find (i) uvu (ii) λu, uλ, uλv given u = a
2 b and v =
b
3 ab.
Solu tion
(i) uvu a b b ab a b
a b aba b
=
=
(
)(
)(
)
2
3
2
2 4
2
(ii) We know that λ is an empty word. Therefore we have
λ
λ
λ
u u
u a b
u v uv
a b b ab
a b ab
=
= =
=
=
=
2
2
3
2 4
(
)(
)
Ì Exam ple 0.1.32: Given A = {a, b, c} check if L 1 , L 2 , L 3 and L 4 are all
languages over the alphabet A., where
L
a aa ab ac abc cab
L
aba aabaa
L
L
a cb
i
1
2
3
4
=
=
=
=
{ , , , ,
,
}
{ ,
}
{ }
{
i
≥ 1}
Solu tion
All the languages L 1 , L 2 , L 3 and L 4 are defined over the alphabet A.
Ì Exam ple 0.1.33:
(a) Given
{
}
L
a b i j
i j
1
1
=
> ≥ and
{
}
L
a b
i j
i j
2
1
=
≤ <
find L
L
1
2
∪ .
(b) Given
{
}
L
a b c i j
i i j
3
1
=
≥
,
and
{
}
L
a b c i j
i j j
4
1
=
≥
,
find L
L
3
4
∩ .
Solu tion
(a)
{
} {
}
{
}
L
L
a b i j
a b
i j
a b i j i j
i j
i j
i j
1
2
1
1
1
∪ =
> ≥ ∪
≤ <
=
≠
≥
, ,
Introduction
25