(b)
{
} {
}
{
}
L
L
a b c i j
a b c i j
a b c i
i i j
i j j
i i i
3
4
1
1
1
∩ =
≥ ∩
≥
=
≠
,
,
Ì Exam ple 0.1.34: Given L 1 is English language and L 2 is French
language, what do you mean by (a) L
L
1
2
∪ and L
L
1
2
∩ .
Solu tion
(a) L
L
1
2
∪ = Set of all sentences someone who speaks both English
and French can recognize.
(b) L
L
1
2
∩ = Language that contains all the sentences that are in both
L 1 and L 2 .
Ì Exam ple 0.1.35: Given A = {a, b, c}, B = {b, c, d} and
{
}
L
a b i
j
i j
1
1
1
=
≥
≥
,
,
{
}
L
b c i j
i j
2
1
=
≥ ≥
{
}
L
a b c d i
j
i j i j
3
1
1
=
≥
≥
,
,
{
}
L
ad a d i
j
i j j
4
2
1
=
≥
≥
( )
,
Determine whether each of the following statements is true or false.
(a) L 1 is a language over A.
(b) L 1 is a language over B.
(c) L 2 is a language over A B
∪ .
(d) L 2 is a language over A B
∩ .
(e) L 3 is a language over A B
∪ .
(f) L 3 is a language over A B
∩ .
(g) L 4 is a language over A B
⊕ .
(h) L 1 is a language over A – B.
(i) L 1 is a language over B – A.
(j) L
L
1
2
∪ is a language over A.
(k) L
L
1
2
∪ is a language over A B
∪ .
(l) L
L
1
2
∪ is a language over A B
∩ .
(m) L
L
1
2
∩ is a language over B.
(n) L
L
1
2
∩ is a language over A B
∪ .
(o) L
L
1
2
∩ is a language over A B
∩ .
Solu tion
From the given sets A and B, we have
A B
a b c d
A B
b c
A B
a
B A d
∪ =
∩ =
− =
− =
{ , , , }
{ , }
{ }
{ }.
26
Theory of Automata, Formal Languages and Computation