Solution Manual For
Introduction to the Theory of Computation 3rd Edition by Michael Sipser Mathematics Department MIT
Chapter 0-10
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams, case
studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make strategic
decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in Business
ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess decision-making skills, as
well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
Chapter 0
0.1 a. The odd positive integers.
b. The even integers.
c. The even positive integers.
d. The positive integers which are a multiple of 6.
e. The palindromes over 0,1 .
f. The empty set.
0.2 a. {1, 10, 100}.
b. {n| n > 5}.
c. {1, 2, 3, 4}.
d. {aba}.
e. {ε}.
f. ∅.
0.3 a. No.
b. Yes.
c. A.
d. B.
e. {(x, x), (x, y), (y, x), (y, y), (z, x), (z, y)}.
f. {∅, {x}, {y}, {x, y}}.
0.4 A × B has ab elements, because each element of A is paired with each element of B, so
A × B contains b elements for each of the a elements of A.
0.5 (C) contains 2c elements because each element of C may either be in (C) or not in
(C), and so each element of C doubles the number of subsets of C. Alternatively, we
can view each subset S of C as corresponding to a binary string b of length c, where S
contains the ith element of C iff the ith place of b is 1. There are 2c strings of length c
and hence that many subsets of C.
0.6 a. f (2) = 7.
b. The range = 6, 7 and the domain = 1, 2, 3, 4, 5 .
c. g(2, 10) = 6.
d. The range = 1, 2, 3, 4, 5 6, 7, 8, 9, 10 and the domain = 6, 7, 8, 9, 10 .
e. f (4) = 7 so g(4,f (4)) = g(4, 7) = 8.
0.7 The underlying set is U in these examples.
a. Let R be the ―within 1‖ relation, that is, R = {(a, b)| |a − b| ≤ 1}.
b. Let R be the ―less than or equal to‖ relation, that is, R = {(a, b)| a ≤ b}.
c. Finding a R that is symmetric and transitive but not reflexive is tricky because of the
following ―near proof‖ that R cannot exist! Assume that R is symmetric and transitive
and chose any member x in the underlying set. Pick any other member y in the underlying
set for which (x, y)∈ R. Then (y, x) ∈R because R is symmetric and so (x, x)∈ R
because R is transitive, hence R is reflexive. This argument fails to be an actual proof
because y may fail to exist for x.
Let R be the ―neither side is 1‖ relation, R = {(a, b)| a /= 1 and b /= 1}.
0.10 Let G be any graph with n nodes where n 2. The degree of every node in G is one
of the n possible values from 0 to n 1. We would like to use the pigeon hole principle
, to show that two of these values must be the same, but number of possible values is too
great. However, not all of the values can occur in the same graph because a node of
degree 0 cannot coexist with a node of degree n 1. Hence G can exhibit at most n 1
degree values among its n nodes, so two of the values must be the same.
0.11 The error occurs in the last sentence. If H contains at least 3 horses, H1 and H2 contain
a horse in common, so the argument works properly. But, if H contains exactly 2 horses,
then H1 and H2 each have exactly 1 horse, but do not have a horse in common. Hence
we cannot conclude that the horse in H1 has the same color as the horse in H2. So the 2
horses in H may not be colored the same.
1
0.12 a. Basis: Let n = 0. Then, S(n) = 0 by definition. Furthermore, n(n + 1) = 0. So
2
1
S(n) = n(n + 1) when n = 0.
Induction: Assume true for n = k where k 0 and prove true for n = k + 1. We
can use this series of equalities:
S(k + 1) = 1 + 2 + · · · + k + (k + 1) by definition
= S(k) + (k + 1) because S(k) = 1 + 2 + · · · + k
1
= k(k + 1) + (k + 1) by the induction hypothesis
1
= (k + 1)(k + 2) by algebra
1 4 3 2
b. Basis: Let n = 0. Then, C(n) = 0 by definition, and (n + 2n + n ) = 0. So
4
1 4 3 2
C(n) = (n + 2n + n ) when n = 0.
Induction: Assume true for n = k where k 0 and prove true for n = k + 1. We
can use this series of equalities:
C(k + 1) = 1 + 2 + · · · + k + (k + 1)
3 3 3 3
by definition
C(k) = 1 + · · · + k
3 3 3
= C(k) + (k + 1)
1 4 3 2 3
= (n + 2n + n ) + (k + 1) induction hypothesis
1 4 3 2
= ((n + 1) + 2(n + 1) + (n + 1) ) by algebra
0.13 Dividing by (a b) is illegal, because a = b hence a b = 0 and division by 0 is
undefined.
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams, case
studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make strategic
decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in Business
ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess decision-making skills, as
well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
Chapter 1
1.12 Observe that D ⊆b∗a∗ because D doesn’t contain strings that have ab as a substring.
Hence D is generated by the regular expression (aa)∗b(bb)∗. From this description,
finding the DFA for D is more easily done.
1.14 a. Let M ′ be the DFA M with the accept and non-accept states swapped. We show that M ′
recognizes the complement of B, where B is the language recognized by M . Suppose
M ′ accepts x. If we run M ′ on x we end in an accept state of M ′. Because M and M ′
have swapped accept/non-accept states, if we run M on x, we would end in a non-accept
state. Therefore, x B. Similarly, if x is not accepted by M ′, then it would be accepted
by M . So M ′ accepts exactly those strings not accepted by M . Therefore, M ′ recognizes
the complement of B.
Since B could be any arbitrary regular language and our construction shows how to
build an automaton to recognize its complement, it follows that the complement of any
regular language is also regular. Therefore, the class of regular languages is closed under
complement.
b. Consider the NFA in Exercise 1.16(a). The string a is accepted by this automaton. If we
swap the accept and reject states, the string a is still accepted. This shows that swapping
the accept and non-accept states of an NFA doesn’t necessarily yield a new NFA rec-
ognizing the complementary language. The class of languages recognized by NFAs is,
, however, closed under complement. This follows from the fact that the class of languages
recognized by NFAs is precisely the class of languages recognized by DFAs which we
know is closed under complement from part (a).
1.18 Let Σ = {0, 1}.
a. 1Σ∗0
b. Σ∗1Σ∗1Σ∗1Σ∗
c. Σ∗0101Σ∗
d. ΣΣ0Σ∗
e. (0 ∪ 1Σ)(ΣΣ)∗
f. (0 ∪ (10)∗)∗1∗
g. (ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)
h. Σ∗0Σ∗ ∪ 1111Σ∗ ∪ 1 ∪ ε
i. (1Σ)∗(1 ∪ ε)
j. 0∗(100 ∪ 010 ∪ 001 ∪ 00)0∗
k. ε∪0
l. (1∗01∗01∗)∗ ∪ 0∗10∗10∗
m.
n. Σ+
1.20 a. ab, ε; ba, aba
b. ab, abab; ε, aabb
c. ε, aa; ab, aabb
d. ε, aaa; aa, b
e. aba, aabbaa; ε, abbb
f. aba, bab; ε, ababab
g. b, ab; ε, bb
h. ba, bba; b, ε
1.21 In both parts we first add a new start state and a new accept state. Several solutions are
possible, depending on the order states are removed.
a. Here we remove state 1 then state 2 and we obtain
a∗b(a ba∗b)∗
b. Here we remove states 1, 2, then 3 and we obtain
o ∪ ((a ∪ b)a∗b((b ∪ a(a ∪ b))a∗b)∗(ε ∪ a))
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams, case
studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make strategic
decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in Business
ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess decision-making skills, as
well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
b. /#(#∗(a ∪ b) ∪ /)∗# /
+
1.22
1.24 a. q1, q1, q1, q1; 000.
b. q1, q2, q2, q2; 111.
c. q1, q1, q2, q1, q2; 0101.
d. q1, q3; 1.
e. q1, q3, q2, q3, q2; 1111.
f. q1, q3, q2, q1, q3, q2, q1; 110110.
g. q1; ε.
1.25 A finite state transducer is a 5-tuple (Q, Σ, Γ, δ, q0), where
i) Q is a finite set called the states,
ii) Σ is a finite set called the alphabet,
iii) Γ is a finite set called the output alphabet,
iv) δ : Q Σ Q Γ is the transition function,
v) q0 Q is the start state.
Let M = (Q, Σ, Γ, δ, q0) be a finite state transducer, w = w1w2 wn be a string
over Σ, and v = v1v2 vn be a string over the Γ. Then M outputs v if a sequence of
states r0, r 1 , ... , rn exists in Q with the following two conditions:
i) r0 = qo
ii) δ(ri, wi+1) = (ri+1, vi+1) for i = 0, . . . , n − 1.
, 1.26 a. T1 = (Q, Σ, Γ, δ, q1), where
i) Q = {q1, q2},
ii) Σ = {0, 1, 2},
iii) Γ = {0, 1},
iv) δ is described as
q1 (q1,0) (q1,0) (q2,1)
q2 (q1,0) (q2,1) (q2,1)
v) q1 is the start state.
b. T2 = (Q, Σ, Γ, δ, q1), where
i) Q = {q1, q2, q3},
ii) Σ = {a, b},
iii) Γ = {0, 1},
iv) δ is described as
b
q1 (q2,1) (q3,1)
q2 (q3,1) (q1,0)
q3 (q1,0) (q2,1)
v) q1 is the start state.
1.29 b. Let A2 = www w 0,1 ∗ . We show that A2 is nonregular using the pumping
lemma. Assume to the contrary that A2 is regular. Let p be the pumping length given by
p p p
the pumping lemma. Let s be the string a ba ba b. Because s is a member of A2 and
s has length more than p, the pumping lemma guarantees that s can be split into three
pieces, s = xyz, satisfying the three conditions of the lemma. However, condition 3
implies that y must consist only of as, so xyyz A2 and one of the first two conditions
is violated. Therefore A2 is nonregular.
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams,
case studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make
strategic decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in
Business ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess
decision-making skills, as well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
p p
1.30 The error is that s = 0 1 can be pumped. Let s = xyz, where x = 0, y = 0 and
p 2 p
z = 0 − 1 . The conditions are satisfied because
i) for any i ≥ 0, xy z = 00 0 − 1 is in 0∗1∗.
i i p 2 p
ii) |y| = 1 > 0, and
iii) |xy| = 2 ≤ p.
1.31 We construct a DFA which alternately simulates the DFAs for A and B, one step at a time.
The new DFA keeps track of which DFA is being simulated. Let M1 = (Q1, Σ, δ1, s1, F1)
and M2 = (Q2, Σ, δ2, s2, F2) be DFAs for A and B. We construct the following DFA
M = (Q, Σ, δ, s 0 ,F ) for the perfect shuffle of A and B.
i) Q = Q1 × Q2 × {1, 2}.
ii) For q1 ∈ Q1, q2 ∈ Q2, b ∈ {1, 2}, and a ∈ Σ:
(δ1(q1, a), q2, 2) b = 1
δ((q1, q2, b), a) = (q ,δ (q , a), 1) b = 2.
1 1 2
iii) s0 = (s1, s2, 1).
Introduction to the Theory of Computation 3rd Edition by Michael Sipser Mathematics Department MIT
Chapter 0-10
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams, case
studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make strategic
decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in Business
ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess decision-making skills, as
well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
Chapter 0
0.1 a. The odd positive integers.
b. The even integers.
c. The even positive integers.
d. The positive integers which are a multiple of 6.
e. The palindromes over 0,1 .
f. The empty set.
0.2 a. {1, 10, 100}.
b. {n| n > 5}.
c. {1, 2, 3, 4}.
d. {aba}.
e. {ε}.
f. ∅.
0.3 a. No.
b. Yes.
c. A.
d. B.
e. {(x, x), (x, y), (y, x), (y, y), (z, x), (z, y)}.
f. {∅, {x}, {y}, {x, y}}.
0.4 A × B has ab elements, because each element of A is paired with each element of B, so
A × B contains b elements for each of the a elements of A.
0.5 (C) contains 2c elements because each element of C may either be in (C) or not in
(C), and so each element of C doubles the number of subsets of C. Alternatively, we
can view each subset S of C as corresponding to a binary string b of length c, where S
contains the ith element of C iff the ith place of b is 1. There are 2c strings of length c
and hence that many subsets of C.
0.6 a. f (2) = 7.
b. The range = 6, 7 and the domain = 1, 2, 3, 4, 5 .
c. g(2, 10) = 6.
d. The range = 1, 2, 3, 4, 5 6, 7, 8, 9, 10 and the domain = 6, 7, 8, 9, 10 .
e. f (4) = 7 so g(4,f (4)) = g(4, 7) = 8.
0.7 The underlying set is U in these examples.
a. Let R be the ―within 1‖ relation, that is, R = {(a, b)| |a − b| ≤ 1}.
b. Let R be the ―less than or equal to‖ relation, that is, R = {(a, b)| a ≤ b}.
c. Finding a R that is symmetric and transitive but not reflexive is tricky because of the
following ―near proof‖ that R cannot exist! Assume that R is symmetric and transitive
and chose any member x in the underlying set. Pick any other member y in the underlying
set for which (x, y)∈ R. Then (y, x) ∈R because R is symmetric and so (x, x)∈ R
because R is transitive, hence R is reflexive. This argument fails to be an actual proof
because y may fail to exist for x.
Let R be the ―neither side is 1‖ relation, R = {(a, b)| a /= 1 and b /= 1}.
0.10 Let G be any graph with n nodes where n 2. The degree of every node in G is one
of the n possible values from 0 to n 1. We would like to use the pigeon hole principle
, to show that two of these values must be the same, but number of possible values is too
great. However, not all of the values can occur in the same graph because a node of
degree 0 cannot coexist with a node of degree n 1. Hence G can exhibit at most n 1
degree values among its n nodes, so two of the values must be the same.
0.11 The error occurs in the last sentence. If H contains at least 3 horses, H1 and H2 contain
a horse in common, so the argument works properly. But, if H contains exactly 2 horses,
then H1 and H2 each have exactly 1 horse, but do not have a horse in common. Hence
we cannot conclude that the horse in H1 has the same color as the horse in H2. So the 2
horses in H may not be colored the same.
1
0.12 a. Basis: Let n = 0. Then, S(n) = 0 by definition. Furthermore, n(n + 1) = 0. So
2
1
S(n) = n(n + 1) when n = 0.
Induction: Assume true for n = k where k 0 and prove true for n = k + 1. We
can use this series of equalities:
S(k + 1) = 1 + 2 + · · · + k + (k + 1) by definition
= S(k) + (k + 1) because S(k) = 1 + 2 + · · · + k
1
= k(k + 1) + (k + 1) by the induction hypothesis
1
= (k + 1)(k + 2) by algebra
1 4 3 2
b. Basis: Let n = 0. Then, C(n) = 0 by definition, and (n + 2n + n ) = 0. So
4
1 4 3 2
C(n) = (n + 2n + n ) when n = 0.
Induction: Assume true for n = k where k 0 and prove true for n = k + 1. We
can use this series of equalities:
C(k + 1) = 1 + 2 + · · · + k + (k + 1)
3 3 3 3
by definition
C(k) = 1 + · · · + k
3 3 3
= C(k) + (k + 1)
1 4 3 2 3
= (n + 2n + n ) + (k + 1) induction hypothesis
1 4 3 2
= ((n + 1) + 2(n + 1) + (n + 1) ) by algebra
0.13 Dividing by (a b) is illegal, because a = b hence a b = 0 and division by 0 is
undefined.
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams, case
studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make strategic
decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in Business
ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess decision-making skills, as
well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
Chapter 1
1.12 Observe that D ⊆b∗a∗ because D doesn’t contain strings that have ab as a substring.
Hence D is generated by the regular expression (aa)∗b(bb)∗. From this description,
finding the DFA for D is more easily done.
1.14 a. Let M ′ be the DFA M with the accept and non-accept states swapped. We show that M ′
recognizes the complement of B, where B is the language recognized by M . Suppose
M ′ accepts x. If we run M ′ on x we end in an accept state of M ′. Because M and M ′
have swapped accept/non-accept states, if we run M on x, we would end in a non-accept
state. Therefore, x B. Similarly, if x is not accepted by M ′, then it would be accepted
by M . So M ′ accepts exactly those strings not accepted by M . Therefore, M ′ recognizes
the complement of B.
Since B could be any arbitrary regular language and our construction shows how to
build an automaton to recognize its complement, it follows that the complement of any
regular language is also regular. Therefore, the class of regular languages is closed under
complement.
b. Consider the NFA in Exercise 1.16(a). The string a is accepted by this automaton. If we
swap the accept and reject states, the string a is still accepted. This shows that swapping
the accept and non-accept states of an NFA doesn’t necessarily yield a new NFA rec-
ognizing the complementary language. The class of languages recognized by NFAs is,
, however, closed under complement. This follows from the fact that the class of languages
recognized by NFAs is precisely the class of languages recognized by DFAs which we
know is closed under complement from part (a).
1.18 Let Σ = {0, 1}.
a. 1Σ∗0
b. Σ∗1Σ∗1Σ∗1Σ∗
c. Σ∗0101Σ∗
d. ΣΣ0Σ∗
e. (0 ∪ 1Σ)(ΣΣ)∗
f. (0 ∪ (10)∗)∗1∗
g. (ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)
h. Σ∗0Σ∗ ∪ 1111Σ∗ ∪ 1 ∪ ε
i. (1Σ)∗(1 ∪ ε)
j. 0∗(100 ∪ 010 ∪ 001 ∪ 00)0∗
k. ε∪0
l. (1∗01∗01∗)∗ ∪ 0∗10∗10∗
m.
n. Σ+
1.20 a. ab, ε; ba, aba
b. ab, abab; ε, aabb
c. ε, aa; ab, aabb
d. ε, aaa; aa, b
e. aba, aabbaa; ε, abbb
f. aba, bab; ε, ababab
g. b, ab; ε, bb
h. ba, bba; b, ε
1.21 In both parts we first add a new start state and a new accept state. Several solutions are
possible, depending on the order states are removed.
a. Here we remove state 1 then state 2 and we obtain
a∗b(a ba∗b)∗
b. Here we remove states 1, 2, then 3 and we obtain
o ∪ ((a ∪ b)a∗b((b ∪ a(a ∪ b))a∗b)∗(ε ∪ a))
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams, case
studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make strategic
decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in Business
ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess decision-making skills, as
well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
b. /#(#∗(a ∪ b) ∪ /)∗# /
+
1.22
1.24 a. q1, q1, q1, q1; 000.
b. q1, q2, q2, q2; 111.
c. q1, q1, q2, q1, q2; 0101.
d. q1, q3; 1.
e. q1, q3, q2, q3, q2; 1111.
f. q1, q3, q2, q1, q3, q2, q1; 110110.
g. q1; ε.
1.25 A finite state transducer is a 5-tuple (Q, Σ, Γ, δ, q0), where
i) Q is a finite set called the states,
ii) Σ is a finite set called the alphabet,
iii) Γ is a finite set called the output alphabet,
iv) δ : Q Σ Q Γ is the transition function,
v) q0 Q is the start state.
Let M = (Q, Σ, Γ, δ, q0) be a finite state transducer, w = w1w2 wn be a string
over Σ, and v = v1v2 vn be a string over the Γ. Then M outputs v if a sequence of
states r0, r 1 , ... , rn exists in Q with the following two conditions:
i) r0 = qo
ii) δ(ri, wi+1) = (ri+1, vi+1) for i = 0, . . . , n − 1.
, 1.26 a. T1 = (Q, Σ, Γ, δ, q1), where
i) Q = {q1, q2},
ii) Σ = {0, 1, 2},
iii) Γ = {0, 1},
iv) δ is described as
q1 (q1,0) (q1,0) (q2,1)
q2 (q1,0) (q2,1) (q2,1)
v) q1 is the start state.
b. T2 = (Q, Σ, Γ, δ, q1), where
i) Q = {q1, q2, q3},
ii) Σ = {a, b},
iii) Γ = {0, 1},
iv) δ is described as
b
q1 (q2,1) (q3,1)
q2 (q3,1) (q1,0)
q3 (q1,0) (q2,1)
v) q1 is the start state.
1.29 b. Let A2 = www w 0,1 ∗ . We show that A2 is nonregular using the pumping
lemma. Assume to the contrary that A2 is regular. Let p be the pumping length given by
p p p
the pumping lemma. Let s be the string a ba ba b. Because s is a member of A2 and
s has length more than p, the pumping lemma guarantees that s can be split into three
pieces, s = xyz, satisfying the three conditions of the lemma. However, condition 3
implies that y must consist only of as, so xyyz A2 and one of the first two conditions
is violated. Therefore A2 is nonregular.
exams include:Multiple Choice Questions (MCQs): These are frequently used to assess students’ understanding of business terminology, theories, and principles.Case Studies: A staple of business exams,
case studies present students with real-world business scenarios and ask them to apply their knowledge to solve complex problems. Case studies evaluate students' ability to think critically and make
strategic decisions.Essay/Short Answer Questions: These types of questions test the student’s ability to explain and analyze business concepts in a detailed and coherent manner.1.3. Skills Tested in
Business ExamsCritical Thinking and Problem-Solving: Business exams often include case studies that challenge students to apply theoretical knowledge to real-life situations. These tests assess
decision-making skills, as well as the ability to evaluate various business alternatives.Quantitative Analysis: For subjects like finance or economics, business exa
p p
1.30 The error is that s = 0 1 can be pumped. Let s = xyz, where x = 0, y = 0 and
p 2 p
z = 0 − 1 . The conditions are satisfied because
i) for any i ≥ 0, xy z = 00 0 − 1 is in 0∗1∗.
i i p 2 p
ii) |y| = 1 > 0, and
iii) |xy| = 2 ≤ p.
1.31 We construct a DFA which alternately simulates the DFAs for A and B, one step at a time.
The new DFA keeps track of which DFA is being simulated. Let M1 = (Q1, Σ, δ1, s1, F1)
and M2 = (Q2, Σ, δ2, s2, F2) be DFAs for A and B. We construct the following DFA
M = (Q, Σ, δ, s 0 ,F ) for the perfect shuffle of A and B.
i) Q = Q1 × Q2 × {1, 2}.
ii) For q1 ∈ Q1, q2 ∈ Q2, b ∈ {1, 2}, and a ∈ Σ:
(δ1(q1, a), q2, 2) b = 1
δ((q1, q2, b), a) = (q ,δ (q , a), 1) b = 2.
1 1 2
iii) s0 = (s1, s2, 1).
