Therefore we have
|| ||
|| || || ||.
uv m n u
v
= + =
+
(b) Now,
|| || | || || || (
|| || || ||
|| || ||
uv
u
v
v
u
uv
=
+
⇒
=
+
⇒
=
from (a))
vu||.
¨
Ì Exam ple 0.1.28: Given A = {a, b, c}, find L
* where
(i) L = {b
2 } (ii) L = {a, b} (iii) L = {a,b, c
3 }
Solu tion
(i) For L = {b
2 }, L
* has all words b
n , where n is even (including the
empty word λ).
(ii) For L = {a, b}, L* has words in a and b.
(iii) For L a b c
= { , , }
3
L* has all words from A = {a, b, c} with the length of each maximal subword
composed entirely of C’s is divisible by 3.
Ì Exam ple 0.1.29: For the language L = {ab, c} over the set A = {a, b, c}.
Find (a) L
3 (b) L
–2 (c) L
0 .
Solu tion
(a) For L = {ab, c}, we have
L
L
ababab, ababc, abca
3
= All 3 - word sequences from
= {
}
b, abc ,cabab,cabc,c ab,c
2
2
3
(b) L
–2 is “Not defined” as negative power of a language is not
defined.
(c) L
0 = {λ}, where λ is empty word.
Ì Exam ple 0.1.30: Given L 1 = {a, ab, a
2 } and L 2 = {b
2 , aba} are the
languages over A = {a, b}, determine {a} L 1 L 2 (b) L 2 L 2 .
Solu tion:
(a) To find L 1 L 2 , we concatenate words in L 1 with words in L 2 so that
{
}
L L
ab a ba ab ababa a b a ba
1 2
2
2
3
2 2
3
=
,
,
,
,
,
24
Theory of Automata, Formal Languages and Computation