An Introduction to Formal Languages and Automata Seventh Edition Linz SOLUTION MANUAL PDF

,1 1.1 Solutions
1. With S1 = {2, 3, 5, 7}, S2 = {2, 4, 5, 8, 9} and U = {1 : 10} compute
S
S1 S2 .

S2 = {1, 2, 4, 5, 6, 8, 9, 10}.
S
Solution: S1

2. With S1 = {2, 3, 5, 7} and S2 = {2, 4, 5, 8, 9}, compute S1 × S2 and
S2 × S1 .

Solution: S1 ×S2 = {(2, 2), (2, 4), (2, 5), (2, 8), (2, 9), (3, 2), (3, 4), (3, 5), (3, 8), (3, 9),
(5, 2), (5, 4), (5, 5), (5, 8), (5, 9), (7, 2), (7, 4), (7, 5), (7, 8), (7, 9)}.
S2 ×S1 = {(2, 2), (4, 2), (5, 2), (8, 2), (9, 2), (2, 3), (4, 3), (5, 3), (8, 3), (9, 3),
(2, 5), (4, 5), (5, 5), (8, 5), (9, 5), (2, 7), (4, 7), (5, 7), (8, 7), (9, 7)}.

3. For S = {2, 5, 6, 8} and T = {2, 4, 6, 8}, compute |S ∩ T | + |S ∪ T |.

Solution: |S ∩ T | + |S ∪ T | = 3 + 5 = 8.

4. What relation between two sets S and T must hold so that |S ∪ T | =
|S| + |T |.

Solution: S and T must be two disjoint sets.

5. ** Show that for all sets S and T , S − T = S ∩ T .

Solution: Suppose x ∈ S − T. Then x ∈ S and x ∈ / T , which means
x ∈ S and x ∈ T , that is x ∈ S ∩ T . So S − T ⊆ S ∩ T . Conversely,
if x ∈ S ∩ T , then x ∈ S and x ∈
/ T , which means x ∈ S − T . That is
S ∩ T ⊆ S − T . Therefore S − T = S ∩ T .

6. ** Prove De Morgan’s laws, Equations (1.2) and (1.3) by showing that
an element x is in the set on one side of the equality, then it must also
be in the set on the other side.

Solution: For Equation (1.2), suppose x ∈ S1 ∪ S2 . Then x ∈ / S1 ∪ S2 ,
which means that x cannot be in S1 or in S2 , that is x ∈ S 1 ∩ S 2 . So
S1 ∪ S2 ⊆ S1 ∩ S2 . Conversely, if x ∈ S 1 ∩ S 2 , then x is not in S1 and
x is not in S2 , that is, x ∈ S1 ∪ S2 . So S1 ∩ S2 ⊆ S1 ∪ S2 . Therefore
S1 ∪ S2 = S1 ∩ S2 .
Similar arguements apply for Equation (1.3).

1

, 7. Show that if S1 ⊆ S2 then S2 ⊆ S1 .

Solution: Suppose x ∈ S2 which means x is not in S2 . Since S1 is a
subset of S2 , so x cannot be in S1 , that is x ∈ S1 . So S2 ⊆ S1 .

8. Show that S1 = S2 if and only if S1 ∪ S2 = S1 ∩ S2 .

Solution: If S1 = S2 , then obviously S1 ∪ S2 = S1 ∩ S2 (= S1 = S2 ).
Conversely, since S1 ∩ S2 ⊆ S1 ⊆ S1 ∪ S2 , so S1 ∪ S2 = S1 ∩ S2 means
S1 = S1 ∪ S2 . Ihe reasoning gives S2 = S1 ∪ S2 . Therefore S1 = S2 .

9. Use induction on the size of S to show that if S is a finite set, then
2S = 2|S| .

Solution: For S = , 2S = { } which means |S| = 0 and 2|S| = 1.
Suppose the conjecture, 2S = 2|S| is true for all sets S with |S| =
0, 1, ..., n.
Let Sn+1 = Sn ∪ {xn+1 } be a set of length n + 1 where |Sn | = n with
2Sn = {Sn,1 , ..., Sn,2n }. Since the power set 2Sn+1 = 2Sn ∪ ({Sn,1 ∪
{xn+1 }, ..., {Sn,2n ∪ {xn+1 }}), so 2Sn+1 = 2Sn + 2Sn = 2 2Sn =
2(2n ) = 2n+1 . This completes the inductive proof.

10. Show that if S1 and S2 are finite sets with |S1 | = n and |S2 | = m, then

|S1 ∪ S2 | ≤ n + m.

Solution: Since S1 ∪ S2 = S1 ∪ (S2 − S1 ) and S1 ∩ (S2 − S1 ) = , so
|S1 ∪ S2 | = |S1 | + |S2 − S1 | ≤ |S1 | + |S2 | = n + m.

11. If S1 and S2 are finite sets, show that |S1 × S2 | = |S1 | |S2 |.

Solution: If S1 = {x1 , ..., xn } and S2 = {y1 , ..., ym }, then by definition
S1 × S2 = {(x1 , y1 ), (x1 , y2 ), ..., (xn , ym )}. That is |S1 × S2 | = nm =
|S1 | |S2 |.

12. **Consider the relation between two sets defined by S1 ≡ S2 if and
only if |S1 | = |S2 |. Show that this is an equivalence relation.




2

, Solution: Check the three rules of equivalence relation for any sets
S1 , S2 as follows :
a) reflexivity: Since |S1 | = |S1 |, so S1 ≡ S1 .
b) symmetry: if S1 ≡ S2 , then |S1 | = |S2 |. So |S2 | = |S1 | which means
S2 ≡ S1 .
c) transitivity: if S1 ≡ S3 and S3 ≡ S2 , then |S1 | = |S3 | = |S2 |. Hence
S1 ≡ S2 .

13. Occasionally, we need to use the union and intersection symbols in a
manner analogous to the summation sign Σ. We define
[
Sp = Si ∪ Sj ∪ Sk · · ·
p∈{i,j,k,...}

with an analogous notation for the intersection of several sets.
With this notation, the general DeMorgan’s laws are written as
[ \
Sp = Sp
p∈P p∈P

and \ [
Sp = Sp .
p∈P p∈P

Prove these identities when P is a finite set.

Solution: This can be proven by an induction on the number of sets.
Let Z = S1 ∪ S2 ... ∪ Sn . Then S1 ∪ S2 ... ∪ Sn ∪ Sn+1 = Z ∪ Sn+1 . By
the standard De Morgan’s law,

Z ∪ Sn+1 = Z ∩ S n+1 .

With the inductive assumption, the relation is true for up to n sets,
that is,
Z = S 1 ∩ S 2 ∩ ...∩S n .

Therefore,
Z ∪ Sn+1 = S 1 ∩ S 2 ∩ ...∩S n ∩ S n+1 ,

completing the inductive step.

3

,14. Show that
S1 ∪ S2 = S 1 ∩ S 2 .

Solution: By the DeMorgan’s laws and the fact S = S, we have

S 1 ∩ S 2 = S1 ∪ S2 = S1 ∪ S2 .

15. Show that S1 = S2 if and only if
   
S1 ∩ S 2 ∪ S 1 ∩ S2 = .

Solution:
 Suppose
   S2 . Then S1 ∩ S 2 = S1 ∩ S2 = S1 ∩ S 1 =
S1 = ,
so S1 ∩ S 2 ∪ S 1 ∩ S2 = ∪ = .
   
Suppose that S1 ∩ S 2 ∪ S 1 ∩ S2 = . Now if S1 6= S2 , then there
must
 be an element
 x inS1 but not in S2 which means S1 ∩ S 2 6= .
So S1 ∩ S 2 ∪ S 1 ∩ S2 6= . This contradics the assumption. So
S1 = S2 and the proof is completed.

16. Show that  
S1 ∪ S2 − S1 ∩ S 2 = S2 .

Solution: If we use the distributive law in the next exercise problem,
then S1 ∪ S2 − (S1 ∩ S2 ) = (S1 ∪ S2 ) ∩ (S1 ∩ S2 ) = (S1 ∪ S2 ) ∩ (S1 ∪ S2 )
= ((S1 ∪ S2 ) ∩ S1 ) ∪ ((S1 ∪ S2 ) ∩ S2 )) = (S2 ∩ S1 ) ∪ S2 = S2 .

17. Show that the distributive law

S1 ∩ (S2 ∪ S3 ) = (S1 ∩ S2 ) ∪ (S1 ∩ S3 )

holds for sets.

Solution: x ∈ S1 ∩ (S2 ∪ S3 )
if and only if x ∈ S1 and x ∈ (S2 ∪ S3 )
if and only if x ∈ S1 and (x ∈ S2 or x ∈ S3 )
if and only if (x ∈ S1 and x ∈ S2 ) or (x ∈ S1 and x ∈ S3 )
if and only if x ∈ (S1 ∩ S2 ) or (S1 ∩ S3 ) = (S1 ∩ S2 ) ∪ (S1 ∩ S3 ).


4

,18. Show that
S1 × (S2 ∪ S3 ) = (S1 × S2 ) ∪ (S1 × S3 ) .

Solution: (x, y) ∈ S1 × (S2 ∪ S3 ) if and only if x ∈ S1 and y ∈ (S2 ∪ S3 )
if and only if x ∈ S1 and (y ∈ S2 or y ∈ S3 )
if and only if (x ∈ S1 and y ∈ S2 ) or (x ∈ S1 and y ∈ S3 )
if and only if (x, y) ∈ (S1 × S2 ) or (x, y) ∈ (S1 × S3 )
if and only if (x, y) ∈ (S1 × S2 ) ∪ (S1 × S3 ) .

19. Give conditions on S1 and S2 necessary and sufficient to ensure that

S1 = (S1 ∪ S2 ) − S2 .

Solution: S1 = (S1 ∪S2 )−S2 = (S1 ∪S2 )∩S2 = (S1 ∩S 2 )∪(S2 ∩S 2 ) =
S1 ∩ S 2 . Since S1 = S1 ∩ S 2
if and only if S1 ⊆ S 2 if and only if S1 ∩ S2 = .
Therefore the necessary and sufficient condition to ensure the given
equation is S1 ∩ S2 = .

20. ** Use the equivalence defined in Example 1.4 to partition the set
{2, 4, 5, 6, 9, 23, 24, 25, 31, 37} into equivalence classes.

Solution: The three equivalent classes are: E0 = {6, 9, 24}; E1 =
{4, 25, 31, 37} and E2 = {2, 5, 23}.

21. Show that if f (n) = O (g (n)) and g (n) = O (f (n)), then f (n) =
Θ (g (n)).

Solution: If f (n) = O(g(n)), then f (n) ≤ c1 |g(n)| for some constant
c1 . If g(n) = O(f (n)), then g(n) ≤ c2 |f (n)| for some constant c2 which
means c12 g(n) ≤ |f (n)|. Therefore c12 |g(n)| ≤ |f (n)| ≤ c1 |g(n)|, that is
f (n) = Θ(g(n)).

22. Show that 2n = O (3n ) but 2n =
6 Θ (3n ).

Solution: Since 2n ≤ 3n so 2n = O(3n ). To show that 2n = 6 Θ(3n ).
n n
Suppose 2 = Θ(3 ), then there must exists a constant c > 0 such that

2n ≤ 3n ≤ c2n

5

, for sufficiently large n. Dividing through the inequality by 2n , then
 n
3 3n
= ≤ c.
2 2n
 n
It is not possible, because 32 is unbounded . This contradiction leads
to the conclusion 2n 6= Θ (3n ).

23. Show that the following order-of-magnitude results hold.
(a) n2 + 5 log n = O (n2 ).
(b) 3n = O (n!).
(c) n! = O (nn ).

Solution: (a) n2 + 5 log n ≤ n2 + 5n2 = 6n2 for n ≥ 1. Therefore,
n2 + 5 log n = O (n2 ).
(b)
3n 1 3333 3 1 3 3
   
= .... = ... ≤1
9n! 9 1234 n 2 4 n
for all n ≥ 0. Therefore, 3n = O (n!).
(c) Since
n! nn−1 2 1
n
= ...
n n n nn
is the product of factors less than or equal to one. Therefore, n! =
O (nn ).

24. Show that (n3 − 2n)/(n + 1) = Θ(n2 ).

Solution: Since n2 − n − 4 = (n − 1/2)2 − 17/4 > 0, so n3 − n2 − 4n > 0
for all n ≥ 3. Therefore, n3 − 4n > n2 . Adding n3 on both sides, we
get 2(n3 − 2n) > n3 + n2 which is equivalent to (n3 − 2n) > (n3 + n2 )/2.
Hence, n2 /2 = {(n3 + n2 )/2}/(n + 1) < (n3 − 2n)/(n + 1).
It is obvious that (n3 − 2n)/(n + 1) < (n3 + n2 )/(n + 1) = n2 for all
n ≥ 3. Therefore, n2 /2 < (n3 − 2n)/(n + 1) < n2 for n ≥ 3 shows
(n3 − 2n)/(n + 1) = Θ(n2 ).
n3
25. Show that log (n+1)
= O(n3 ) but not O(n2 ).


6

, n3 n3 n3
Solution: Since log(n+1)
≤ log(2)
for n ≥ 1, therefore log(n+1)
= O(n3 ).
n3
Suppose log (n+1) = O(n2 ), then there exists a constant c such that n3 ≤
cn2 log(n + 1) which means n ≤ c log(n + 1) ≤ 2c log(n) for sufficiently
n3
6 O(log(n)). Therefore, log (n+1)
large n. This is not possible because n =
is not O(n2 ).

26. ** What is wrong with the following argument? x = O(n4 ), y = O(n2 ),
therefore x/y = O(n2 ).

Solution: Since O(x) is any upper bound for x, it is not unique.
Same for O(y). So ordinary arithmetic operations are not neceesary
applicable. For example, take x = n3 and y = n12 , then by the definition
x = O(n4 ), y = O(n2 ). However, x/y = n5 which is not O(n2 ).

27. What is wrong with the following argument? x = Θ(n4 ), y = Θ(n2 ),
therefore xy = Θ(n2 ).

Solution: Nothing is wrong. The argument is correct. Since x =
Θ(n4 ), y = Θ(n2 ), gives c1 n4 ≤ x ≤ c2 n4 and c3 n2 ≤ y ≤ c4 n2 for
constants c1 , c2 , c3 , c4 and sufficiently large n. Therefore, cc14 n2 ≤ xy ≤
c2 2
c3
n . That is xy = Θ(n2 ).

28. Prove that if f (n) = O (g (n)) and g (n) = O (h (n)), then f (n) =
O (h (n)).

Solution: If f (n) = O(g(n)) and g(n) = O(h(n)), then f (n) ≤
c1 |g(n)| and g(n) ≤ c2 |h(n)| for constants c1 , c2 and sufficiently large
n. Thereofe, f (n) ≤ c1 c2 |h(n)| which means f (n) = O (h (n)).

29. Show that if f (n) = O (n2 ) and g (n) = O (n3 ), then
 
f (n) + g (n) = O n3

and  
f (n) g (n) = O n6 .

In this case, is it true that g (n) /f (n) = O (n)?




7

, Solution: If f (n) = O (n2 ) and g (n) = O (n3 ), then f (n) ≤ c1 n2
and g(n) ≤ c2 n3 for constants c1 , c2 and sufficiently large n. So f (n) +
g(n) ≤ c1 n2 + c2 n3 < (c1 + c2 )n3 and f (n)g(n) ≤ (c1 n2 )(c2 n3 ) <
(c1 c2 )n5 < (c1 c2 )n6 . That is f (n) + g (n) = O (n3 ) and f (n) g (n) =
O (n6 ).
By the same reason as Exercise 26, g(n)/f (n) = O(n) is not always
true.

30. ** Assume that f (n) = 2n2 + n and g (n) = O (n2 ). What is wrong
with the following argument?
 
f (n) = O n2 + O (n) ,

so that    
f (n) − g (n) = O n2 + O (n) − O n2 .
Therefore,
f (n) − g (n) = O (n) .

Solution: Ordinary arithmetic operations do not apply to order of
magnitud eargumentsl. That is O(n2 ) − O(n2 ) does not necessarily
equal to 0. For example, in this problem if g(n) = n2 , then f (n) −
g(n) = n2 + n = O(n2 ).

31. Show that if f (n) = Θ(log2 n), then f (n) = Θ(log10 n).

Solution: If f (n) = Θ(log2 n), then c1 log2 n ≤ |f (n)| ≤ c2 log2 n for
constant c1 , c2 and sufficiently large n. Since log2 n = log2 10 log10 n,
so d1 log10 n ≤ |f (n)| ≤ d2 log10 n where d1 = c1 log2 10 and d2 =
c2 log2 10. That is f (n) = Θ(log10 n).

32. Draw a picture of the graph with vertices {v1 , v2 , v3 } and edges {(v1 , v1 ) ,
(v1 , v2 ) , (v2 , v3 ) , (v2 , v1 ) , (v3 , v1 )}. Enumerate all cycles with base v1 .

Solution: The graph is given as follows.




8

, 33. Construct a graph with five vertices, ten edges, and no cycles.
Solution: The graph with five vertices {v1 , v2 , v3 , v4 , v5 } and ten edges
{(v1 , v2 ) ,
(v1 , v3 ) , (v1 , v4 ) , (v1 , v5 ) , (v2 , v3 ) , (v2 , v4 ) , (v2 , v5 ) , (v3 , v4 ) , (v3 , v5 ) , (v4 , v5 )}
has no cycles.




34. Let G = (V, E) be any graph. Prove the following claim: If there is
any walk between vi ∈ V and vj ∈ V , then there must be a path of
length no larger than |V | − 1 between these two vertices.
Solution: To simplify the problem, we assume that there is no edge of
form (v, v) in a walk. Otherwise we remove it from the walk and will
not affect the result of this problem.
If the walk from vi to vj has no repeated vertices, then it is a simple
path. In this case, every vertex in the path has been passed only once.
Hence the length of the path cannot exceed |V | − 1.

9