Ì Exam ple 0.1.23: Given
{
}
L
a b n
n n
=
≥
:
0
obtain (a) L
2 (b) L
R .
Solu tion
Given
{
}
L
a b n
n n
=
≥
: 0
(a)
{
}
L
a b a b n
m
n n m m
2
0
0
=
≥
≥
:
,
where n and m are unrelated.
For example, the string aabbaaabbb is in L
2 .
(b) Reverse of L is given by
{
}
L
b a n
R
n n
=
≥
: 0
Ì Exam ple 0.1.24: Let L = {ab, aa, baa}. Which of the following strings
are in L
* .
(a) abaabaaabaa
(b) aaaabaaaa
(c) baaaaabaaaab
(d) baaaaabaa
Solu tion
Please note that L
* is the “star-closure” of a language L, given by
L L
L
L
*
=
∪ ∪
0
1
2 KK
and L
+ is the “positive closure” defined by
L
L
L
+
= ∪
1
2 KK
(a) ab aa baa ab aa → This string is in L
*
(b) aa aa baa aa → This string is in L
*
(c) baa aa ab aa aa b
baa aa ab aa a ab
undefined
undefined
or
↑
↑
(
)
(
)
This string is not in L
* .
(d) baa aa ab aa → This string is in L
*
.
Ì Exam ple 0.1.25: Given
{
}
L
a b
n
n n
=
≥
+1
0
:
.
It is true that L = L
* for the given language L?
22
Theory of Automata, Formal Languages and Computation