All 30 Chapters & Appendix A & B Covered
SOLUTIONS MANUAL
,Automata, Computability and
Complexity with Applications
Exercises in the Book
Solutions
Elaine Rich
, Part I: Introduction
1 Why Study Automata Theory?
2 Languages and Strings
1) Consider the language L = {1n2n : n > 0}. Is the string 122 in L?
No. Every string in L must have the same number of 1’s as 2’s.
2) Let L1 = {anbn : n > 0}. Let L2 = {cn : n > 0}. For each of the following strings, state whether or not it is an
element of L1L2:
a) ε. No.
b) aabbcc. Yes.
c) abbcc. No.
d) aabbcccc. Yes.
3) Let L1 = {peach, apple, cherry} and L2 = {pie, cobbler, ε}. List the elements of L1L2 in lexicographic
order.
apple, peach, cherry, applepie, peachpie, cherrypie, applecobbler, peachcobbler,
cherrycobbler (We list the items shortest first. Within a given length, we list the items
alphabetically.)
4) Let L = {w ∈ {a, b}* : |w| ≡3 0}. List the first six elements in a lexicographic enumeration of L.
ε, aaa, aab, aba, abb, baa
5) Consider the language L of all strings drawn from the alphabet {a, b} with at least two different substrings of
length 2.
a) Describe L by writing a sentence of the form L = {w ∈ Σ* : P(w)}, where Σ is a set of symbols and P is a
first-order logic formula. You may use the function |s| to return the length of s. You may use all the
standard relational symbols (e.g., =, ≠, <, etc.), plus the predicate Substr(s, t), which is True iff s is a
substring of t.
L = {w ∈ {a, b}* : ∃x, y (x ≠ y ∧ |x| = 2 ∧ |y| = 2 ∧ Substr(x, w) ∧ Substr(y, w))}.
b) List the first six elements of a lexicographic enumeration of L.
aab, aba, abb, baa, bab, bba
6) For each of the following languages L, give a simple English description. Show two strings that are in L and
two that are not (unless there are fewer than two strings in L or two not in L, in which case show as many as
possible).
a) L = {w ∈ {a, b}* : exactly one prefix of w ends in a}.
L is the set of strings composed of zero or more b’s and a single a. a, bba and bbab are in L. bbb and
aaa are not.
b) L = {w ∈ {a, b}* : all prefixes of w end in a}.
L = ∅, since ε is a prefix of every string and it doesn’t end in a. So all strings are not in L, including a and
aa.
Chapter 2 1
, c) L = {w ∈ {a, b}* : ∃x ∈ {a, b}+ (w = axa)}.
L is the set of strings over the alphabet {a, b} whose length is at least 3 and that start and end with a. aba,
and aaa are in L. ε, a, ab and aa are not.
7) Are the following sets closed under the following operations? If not, what are their respective closures?
a) The language {a, b} under concatenation.
Not closed. {w ∈ {a, b}* : |w| > 0}
b) The odd length strings over the alphabet {a, b} under Kleene star.
Not closed because, if two odd length strings are concatenated, the result is of even length. The closure is
the set of all nonempty strings drawn from the alphabet {a, b}.
c) L = {w ∈ {a, b}*} under reverse.
Closed. L includes all strings of a’s and b’s, so, since reverse must also generate strings of a’s and b’s,
any resulting string must have been in the original set.
d) L = {w ∈ {a, b}* : w starts with a} under reverse.
Not closed. L includes strings that end in b. When such strings are reversed, they start with b, so they are
not in L. But, when any string in L is reversed, it ends in a. So the closure is {w ∈ {a, b}* : w starts with
a} ∪ {w ∈ {a, b}* : w ends with a}.
e) L = {w ∈ {a, b}* : w ends in a} under concatenation.
Closed.
8) For each of the following statements, state whether it is True or False. Prove your answer.
a) ∀L1, L2 (L1 = L2 iff L1* = L2*).
False. Counterexample: L1 = {a}. L2 = {a}*. But L1* = L2* = {a}* ≠ {a}.
b) (∅ ∪ ∅*) ∩ (¬∅ – (∅∅*)) = ∅ (where ¬∅ is the complement of ∅).
False. The left hand side equals {ε}, which is not equal to ∅.
c) Every infinite language is the complement of a finite language.
False. Counterexample: Given some nonempty alphabet Σ, the set of all even length strings is an infinite
language. Its complement is the set of all odd length strings, which is also infinite.
d) ∀L ((LR)R = L).
True.
e) ∀L1, L2 ((L1 L2)* = L1* L2*).
False. Counterexample: L1 = {a}. L2 = {b}. (L1 L2)* = (ab)*. L1* L2* = a*b*.
Chapter 2 2
SOLUTIONS MANUAL
,Automata, Computability and
Complexity with Applications
Exercises in the Book
Solutions
Elaine Rich
, Part I: Introduction
1 Why Study Automata Theory?
2 Languages and Strings
1) Consider the language L = {1n2n : n > 0}. Is the string 122 in L?
No. Every string in L must have the same number of 1’s as 2’s.
2) Let L1 = {anbn : n > 0}. Let L2 = {cn : n > 0}. For each of the following strings, state whether or not it is an
element of L1L2:
a) ε. No.
b) aabbcc. Yes.
c) abbcc. No.
d) aabbcccc. Yes.
3) Let L1 = {peach, apple, cherry} and L2 = {pie, cobbler, ε}. List the elements of L1L2 in lexicographic
order.
apple, peach, cherry, applepie, peachpie, cherrypie, applecobbler, peachcobbler,
cherrycobbler (We list the items shortest first. Within a given length, we list the items
alphabetically.)
4) Let L = {w ∈ {a, b}* : |w| ≡3 0}. List the first six elements in a lexicographic enumeration of L.
ε, aaa, aab, aba, abb, baa
5) Consider the language L of all strings drawn from the alphabet {a, b} with at least two different substrings of
length 2.
a) Describe L by writing a sentence of the form L = {w ∈ Σ* : P(w)}, where Σ is a set of symbols and P is a
first-order logic formula. You may use the function |s| to return the length of s. You may use all the
standard relational symbols (e.g., =, ≠, <, etc.), plus the predicate Substr(s, t), which is True iff s is a
substring of t.
L = {w ∈ {a, b}* : ∃x, y (x ≠ y ∧ |x| = 2 ∧ |y| = 2 ∧ Substr(x, w) ∧ Substr(y, w))}.
b) List the first six elements of a lexicographic enumeration of L.
aab, aba, abb, baa, bab, bba
6) For each of the following languages L, give a simple English description. Show two strings that are in L and
two that are not (unless there are fewer than two strings in L or two not in L, in which case show as many as
possible).
a) L = {w ∈ {a, b}* : exactly one prefix of w ends in a}.
L is the set of strings composed of zero or more b’s and a single a. a, bba and bbab are in L. bbb and
aaa are not.
b) L = {w ∈ {a, b}* : all prefixes of w end in a}.
L = ∅, since ε is a prefix of every string and it doesn’t end in a. So all strings are not in L, including a and
aa.
Chapter 2 1
, c) L = {w ∈ {a, b}* : ∃x ∈ {a, b}+ (w = axa)}.
L is the set of strings over the alphabet {a, b} whose length is at least 3 and that start and end with a. aba,
and aaa are in L. ε, a, ab and aa are not.
7) Are the following sets closed under the following operations? If not, what are their respective closures?
a) The language {a, b} under concatenation.
Not closed. {w ∈ {a, b}* : |w| > 0}
b) The odd length strings over the alphabet {a, b} under Kleene star.
Not closed because, if two odd length strings are concatenated, the result is of even length. The closure is
the set of all nonempty strings drawn from the alphabet {a, b}.
c) L = {w ∈ {a, b}*} under reverse.
Closed. L includes all strings of a’s and b’s, so, since reverse must also generate strings of a’s and b’s,
any resulting string must have been in the original set.
d) L = {w ∈ {a, b}* : w starts with a} under reverse.
Not closed. L includes strings that end in b. When such strings are reversed, they start with b, so they are
not in L. But, when any string in L is reversed, it ends in a. So the closure is {w ∈ {a, b}* : w starts with
a} ∪ {w ∈ {a, b}* : w ends with a}.
e) L = {w ∈ {a, b}* : w ends in a} under concatenation.
Closed.
8) For each of the following statements, state whether it is True or False. Prove your answer.
a) ∀L1, L2 (L1 = L2 iff L1* = L2*).
False. Counterexample: L1 = {a}. L2 = {a}*. But L1* = L2* = {a}* ≠ {a}.
b) (∅ ∪ ∅*) ∩ (¬∅ – (∅∅*)) = ∅ (where ¬∅ is the complement of ∅).
False. The left hand side equals {ε}, which is not equal to ∅.
c) Every infinite language is the complement of a finite language.
False. Counterexample: Given some nonempty alphabet Σ, the set of all even length strings is an infinite
language. Its complement is the set of all odd length strings, which is also infinite.
d) ∀L ((LR)R = L).
True.
e) ∀L1, L2 ((L1 L2)* = L1* L2*).
False. Counterexample: L1 = {a}. L2 = {b}. (L1 L2)* = (ab)*. L1* L2* = a*b*.
Chapter 2 2
