EXERCISES 83

EXERCISES
A
1.1 The following are the state diagrams of two DFAs, M1 and M2 . Answer the follow-
ing questions about each of these machines.

a. What is the start state?

b. What is the set of accept states?
c. What sequence of states does the machine go through on input aabb?
d. Does the machine accept the string aabb?
e. Does the machine accept the string ε?
A
1.2 Give the formal description of the machines M1 and M2 pictured in Exercise 1.1.


1.3 The formal description of a DFA M is {q1 , q2 , q3 , q4 , q5 }, {u, d}, δ, q3 , {q3 } ,
where δ is given by the following table. Give the state diagram of this machine.

u d
q1 q1 q2
q2 q1 q3
q3 q2 q4
q4 q3 q5
q5 q4 q5

1.4 Each of the following languages is the intersection of two simpler languages. In
each part, construct DFAs for the simpler languages, then combine them using the
construction discussed in footnote 3 (page 46) to give the state diagram of a DFA
for the language given. In all parts, Σ = {a, b}.
a. {w| w has at least three a’s and at least two b’s}
A
b. {w| w has exactly two a’s and at least two b’s}
c. {w| w has an even number of a’s and one or two b’s}
A
d. {w| w has an even number of a’s and each a is followed by at least one b}
e. {w| w starts with an a and has at most one b}
f. {w| w has an odd number of a’s and ends with a b}
g. {w| w has even length and an odd number of a’s}

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 84 CHAPTER 1 / REGULAR LANGUAGES

1.5 Each of the following languages is the complement of a simpler language. In each
part, construct a DFA for the simpler language, then use it to give the state diagram
of a DFA for the language given. In all parts, Σ = {a, b}.
A
a. {w| w does not contain the substring ab}
A
b. {w| w does not contain the substring baba}
c. {w| w contains neither the substrings ab nor ba}
d. {w| w is any string not in a∗ b∗ }
e. {w| w is any string not in (ab+ )∗ }
f. {w| w is any string not in a∗ ∪ b∗ }
g. {w| w is any string that doesn’t contain exactly two a’s}
h. {w| w is any string except a and b}

1.6 Give state diagrams of DFAs recognizing the following languages. In all parts, the
alphabet is {0,1}.
a. {w| w begins with a 1 and ends with a 0}
b. {w| w contains at least three 1s}
c. {w| w contains the substring 0101 (i.e., w = x0101y for some x and y)}
d. {w| w has length at least 3 and its third symbol is a 0}
e. {w| w starts with 0 and has odd length, or starts with 1 and has even length}
f. {w| w doesn’t contain the substring 110}
g. {w| the length of w is at most 5}
h. {w| w is any string except 11 and 111}
i. {w| every odd position of w is a 1}
j. {w| w contains at least two 0s and at most one 1}
k. {ε, 0}
l. {w| w contains an even number of 0s, or contains exactly two 1s}
m. The empty set
n. All strings except the empty string

1.7 Give state diagrams of NFAs with the specified number of states recognizing each
of the following languages. In all parts, the alphabet is {0,1}.
A
a. The language {w| w ends with 00} with three states
b. The language of Exercise 1.6c with five states
c. The language of Exercise 1.6l with six states
d. The language {0} with two states
e. The language 0∗ 1∗ 0+ with three states
A
f. The language 1∗ (001+ )∗ with three states
g. The language {ε} with one state
h. The language 0∗ with one state

1.8 Use the construction in the proof of Theorem 1.45 to give the state diagrams of
NFAs recognizing the union of the languages described in
a. Exercises 1.6a and 1.6b.
b. Exercises 1.6c and 1.6f.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 EXERCISES 85

1.9 Use the construction in the proof of Theorem 1.47 to give the state diagrams of
NFAs recognizing the concatenation of the languages described in
a. Exercises 1.6g and 1.6i.
b. Exercises 1.6b and 1.6m.
1.10 Use the construction in the proof of Theorem 1.49 to give the state diagrams of
NFAs recognizing the star of the languages described in
a. Exercise 1.6b.
b. Exercise 1.6j.
c. Exercise 1.6m.
A
1.11 Prove that every NFA can be converted to an equivalent one that has a single accept
state.
1.12 Let D = {w| w contains an even number of a’s and an odd number of b’s and does
not contain the substring ab}. Give a DFA with five states that recognizes D and a
regular expression that generates D. (Suggestion: Describe D more simply.)
1.13 Let F be the language of all strings over {0,1} that do not contain a pair of 1s that
are separated by an odd number of symbols. Give the state diagram of a DFA with
five states that recognizes F . (You may find it helpful first to find a 4-state NFA for
the complement of F .)
1.14 a. Show that if M is a DFA that recognizes language B, swapping the accept
and nonaccept states in M yields a new DFA recognizing the complement of
B. Conclude that the class of regular languages is closed under complement.
b. Show by giving an example that if M is an NFA that recognizes language
C, swapping the accept and nonaccept states in M doesn’t necessarily yield
a new NFA that recognizes the complement of C. Is the class of languages
recognized by NFAs closed under complement? Explain your answer.
1.15 Give a counterexample to show that the following construction fails to prove The-
orem 1.49, the closure of the class of regular languages under the star operation.7
Let N1 = (Q1 , Σ, δ1 , q1 , F1 ) recognize A1 . Construct N = (Q1 , Σ, δ, q1 , F ) as
follows. N is supposed to recognize A∗1 .
a. The states of N are the states of N1 .
b. The start state of N is the same as the start state of N1 .
c. F = {q1 } ∪ F1 .
The accept states F are the old accept states plus its start state.
d. Define δ so that for any q ∈ Q1 and any a ∈ Σε ,
(
δ1 (q, a) q 6∈ F1 or a 6= ε
δ(q, a) =
δ1 (q, a) ∪ {q1 } q ∈ F1 and a = ε.

(Suggestion: Show this construction graphically, as in Figure 1.50.)

7In other words, you must present a finite automaton, N , for which the constructed
1
automaton N does not recognize the star of N1 ’s language.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 86 CHAPTER 1 / REGULAR LANGUAGES

1.16 Use the construction given in Theorem 1.39 to convert the following two nonde-
terministic finite automata to equivalent deterministic finite automata.

1.17 a. Give an NFA recognizing the language (01 ∪ 001 ∪ 010)∗ .

b. Convert this NFA to an equivalent DFA. Give only the portion of the DFA
that is reachable from the start state.
1.18 Give regular expressions generating the languages of Exercise 1.6.
1.19 Use the procedure described in Lemma 1.55 to convert the following regular ex-
pressions to nondeterministic finite automata.
a. (0 ∪ 1)∗ 000(0 ∪ 1)∗
b. (((00)∗ (11)) ∪ 01)∗
c. ∅∗
1.20 For each of the following languages, give two strings that are members and two
strings that are not members—a total of four strings for each part. Assume the
alphabet Σ = {a,b} in all parts.
a. a∗ b∗ e. Σ∗ aΣ∗ bΣ∗ aΣ∗
b. a(ba)∗ b f. aba ∪ bab
c. a∗ ∪ b∗ g. (ε ∪ a)b
d. (aaa)∗ h. (a ∪ ba ∪ bb)Σ∗
1.21 Use the procedure described in Lemma 1.60 to convert the following finite au-
tomata to regular expressions.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 EXERCISES 87

1.22 In certain programming languages, comments appear between delimiters such as

/# and #/. Let C be the language of all valid delimited comment strings. A mem-
ber of C must begin with /# and end with #/ but have no intervening #/. For
simplicity, assume that the alphabet for C is Σ = {a, b, /, #}.
a. Give a DFA that recognizes C.
b. Give a regular expression that generates C.
A
1.23 Let B be any language over the alphabet Σ. Prove that B = B + iff BB ⊆ B.
1.24 A finite state transducer (FST) is a type of deterministic finite automaton whose
output is a string and not just accept or reject . The following are state diagrams of
finite state transducers T1 and T2 .

Each transition of an FST is labeled with two symbols, one designating the input
symbol for that transition and the other designating the output symbol. The two
symbols are written with a slash, /, separating them. In T1 , the transition from
q1 to q2 has input symbol 2 and output symbol 1. Some transitions may have
multiple input–output pairs, such as the transition in T1 from q1 to itself. When
an FST computes on an input string w, it takes the input symbols w1 · · · wn one by
one and, starting at the start state, follows the transitions by matching the input
labels with the sequence of symbols w1 · · · wn = w. Every time it goes along a
transition, it outputs the corresponding output symbol. For example, on input
2212011, machine T1 enters the sequence of states q1 , q2 , q2 , q2 , q2 , q1 , q1 , q1 and
produces output 1111000. On input abbb, T2 outputs 1011. Give the sequence of
states entered and the output produced in each of the following parts.
a. T1 on input 011 e. T2 on input b
b. T1 on input 211 f. T2 on input bbab
c. T1 on input 121 g. T2 on input bbbbbb
d. T1 on input 0202 h. T2 on input ε
1.25 Read the informal definition of the finite state transducer given in Exercise 1.24.
Give a formal definition of this model, following the pattern in Definition 1.5
(page 35). Assume that an FST has an input alphabet Σ and an output alphabet Γ but
not a set of accept states. Include a formal definition of the computation of an FST.
(Hint: An FST is a 5-tuple. Its transition function is of the form δ : Q×Σ−→Q×Γ.)
1.26 Using the solution you gave to Exercise 1.25, give a formal description of the ma-
chines T1 and T2 depicted in Exercise 1.24.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 88 CHAPTER 1 / REGULAR LANGUAGES

1.27 Read the informal definition of the finite state transducer given in Exercise 1.24.
Give the state diagram of an FST with the following behavior. Its input and output
alphabets are {0,1}. Its output string is identical to the input string on the even
positions but inverted on the odd positions. For example, on input 0000111 it
should output 1010010.
1.28 Convert the following regular expressions to NFAs using the procedure given in
Theorem 1.54. In all parts, Σ = {a, b}.
a. a(abb)∗ ∪ b
b. a+ ∪ (ab)+
c. (a ∪ b+ )a+ b+
1.29 Use the pumping lemma to show that the following languages are not regular.
A
a. A1 = {0n 1n 2n | n ≥ 0}
b. A2 = {www| w ∈ {a, b}∗ }
n n
A
c. A3 = {a2 | n ≥ 0} (Here, a2 means a string of 2n a’s.)

1.30 Describe the error in the following “proof” that 0∗ 1∗ is not a regular language. (An
error must exist because 0∗ 1∗ is regular.) The proof is by contradiction. Assume
that 0∗ 1∗ is regular. Let p be the pumping length for 0∗ 1∗ given by the pumping
lemma. Choose s to be the string 0p 1p . You know that s is a member of 0∗ 1∗ , but
Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So
0∗ 1∗ is not regular.

PROBLEMS
1.31 For any string w = w1 w2 · · · wn , the reverse of w, written wR , is the string w in
reverse order, wn · · · w2 w1 . For any language A, let AR = {wR | w ∈ A}.
Show that if A is regular, so is AR .
1.32 Let nh 0 i h 0 i h 0 i h 1 io
Σ3 = 0 , 0 , 1 ,..., 1 .
0 1 0 1

Σ3 contains all size 3 columns of 0s and 1s. A string of symbols in Σ3 gives three
rows of 0s and 1s. Consider each row to be a binary number and let

B = {w ∈ Σ∗3 | the bottom row of w is the sum of the top two rows}.

For example,
h0ih1ih1i h0ih1i
0 0 1 ∈ B, but 0 0 6∈ B.
1 0 0 1 1

Show that B is regular. (Hint: Working with B R is easier. You may assume the
result claimed in Problem 1.31.)

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 PROBLEMS 89

1.33 Let  0   0   1   1 
Σ2 = 0
, 1 , 0 , 1 .
Here, Σ2 contains all columns of 0s and 1s of height two. A string of symbols in
Σ2 gives two rows of 0s and 1s. Consider each row to be a binary number and let
C = {w ∈ Σ∗2 | the bottom row of w is three times the top row}.
For example, 00 01 11 00 ∈ C, but 01 01 10 6∈ C. Show that C is regular.
        

(You may assume the result claimed in Problem 1.31.)

1.34 Let Σ2 be the same as in Problem 1.33. Consider each row to be a binary number
and let
D = {w ∈ Σ∗2 | the top row of w is a larger number than is the bottom row}.
For example, 00 10 11 00 ∈ D, but 00 01 11 00 6∈ D. Show that D is regular.
         

1.35 Let Σ2 be the same as in Problem 1.33. Consider the top and bottom rows to be
strings of 0s and 1s, and let
E = {w ∈ Σ∗2 | the bottom row of w is the reverse of the top row of w}.
Show that E is not regular.
1.36 Let Bn = {ak | k is a multiple of n}. Show that for each n ≥ 1, the language Bn is
regular.
1.37 Let Cn = {x| x is a binary number that is a multiple of n}. Show that for each
n ≥ 1, the language Cn is regular.
1.38 An all-NFA M is a 5-tuple (Q, Σ, δ, q0 , F ) that accepts x ∈ Σ∗ if every possible
state that M could be in after reading input x is a state from F . Note, in contrast,
that an ordinary NFA accepts a string if some state among these possible states is an
accept state. Prove that all-NFAs recognize the class of regular languages.
1.39 The construction in Theorem 1.54 shows that every GNFA is equivalent to a GNFA
with only two states. We can show that an opposite phenomenon occurs for DFAs.
Prove that for every k > 1, a language Ak ⊆ {0,1}∗ exists that is recognized by a
DFA with k states but not by one with only k − 1 states.
1.40 Recall that string x is a prefix of string y if a string z exists where xz = y, and that
x is a proper prefix of y if in addition x 6= y. In each of the following parts, we
define an operation on a language A. Show that the class of regular languages is
closed under that operation.
A
a. NOPREFIX (A) = {w ∈ A| no proper prefix of w is a member of A}.
b. NOEXTEND(A) = {w ∈ A| w is not the proper prefix of any string in A}.
1.41 For languages A and B, let the perfect shuffle of A and B be the language
{w| w = a1 b1 · · · ak bk , where a1 · · · ak ∈ A and b1 · · · bk ∈ B, each ai , bi ∈ Σ}.
Show that the class of regular languages is closed under perfect shuffle.
1.42 For languages A and B, let the shuffle of A and B be the language
{w| w = a1 b1 · · · ak bk , where a1 · · · ak ∈ A and b1 · · · bk ∈ B, each ai , bi ∈ Σ∗ }.
Show that the class of regular languages is closed under shuffle.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 90 CHAPTER 1 / REGULAR LANGUAGES

1.43 Let A be any language. Define DROP-OUT (A) to be the language containing all
strings that can be obtained by removing one symbol from a string in A. Thus,
DROP-OUT (A) = {xz| xyz ∈ A where x, z ∈ Σ∗ , y ∈ Σ}. Show that the class
of regular languages is closed under the DROP-OUT operation. Give both a proof
by picture and a more formal proof by construction as in Theorem 1.47.
A
1.44 Let B and C be languages over Σ = {0, 1}. Define
1
B ← C = {w ∈ B| for some y ∈ C, strings w and y contain equal numbers of 1s}.
1
Show that the class of regular languages is closed under the ← operation.
?
1.45 Let A/B = {w| wx ∈ A for some x ∈ B}. Show that if A is regular and B is any
language, then A/B is regular.
1.46 Prove that the following languages are not regular. You may use the pumping
lemma and the closure of the class of regular languages under union, intersection,
and complement.
a. {0n 1m 0n | m, n ≥ 0}
A
b. {0m 1n | m 6= n}
c. {w| w ∈ {0,1}∗ is not a palindrome}8
?
d. {wtw| w, t ∈ {0,1}+ }

1.47 Let Σ = {1, #} and let

Y = {w| w = x1 #x2 # · · · #xk for k ≥ 0, each xi ∈ 1∗ , and xi 6= xj for i 6= j}.

Prove that Y is not regular.

1.48 Let Σ = {0,1} and let

D = {w| w contains an equal number of occurrences of the substrings 01 and 10}.

Thus 101 ∈ D because 101 contains a single 01 and a single 10, but 1010 6∈ D
because 1010 contains two 10s and one 01. Show that D is a regular language.
1.49 a. Let B = {1k y| y ∈ {0, 1}∗ and y contains at least k 1s, for k ≥ 1}.
Show that B is a regular language.
b. Let C = {1k y| y ∈ {0, 1}∗ and y contains at most k 1s, for k ≥ 1}.
Show that C isn’t a regular language.
A
1.50 Read the informal definition of the finite state transducer given in Exercise 1.24.
Prove that no FST can output wR for every input w if the input and output alpha-
bets are {0,1}.
1.51 Let x and y be strings and let L be any language. We say that x and y are distin-
guishable by L if some string z exists whereby exactly one of the strings xz and yz
is a member of L; otherwise, for every string z, we have xz ∈ L whenever yz ∈ L
and we say that x and y are indistinguishable by L. If x and y are indistinguishable
by L, we write x ≡L y. Show that ≡L is an equivalence relation.

8A palindrome is a string that reads the same forward and backward.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 PROBLEMS 91

A?
1.52 Myhill–Nerode theorem. Refer to Problem 1.51. Let L be a language and let X
be a set of strings. Say that X is pairwise distinguishable by L if every two distinct
strings in X are distinguishable by L. Define the index of L to be the maximum
number of elements in any set that is pairwise distinguishable by L. The index of
L may be finite or infinite.

a. Show that if L is recognized by a DFA with k states, L has index at most k.

b. Show that if the index of L is a finite number k, it is recognized by a DFA
with k states.
c. Conclude that L is regular iff it has finite index. Moreover, its index is the
size of the smallest DFA recognizing it.

1.53 Let Σ = {0, 1, +, =} and

ADD = {x=y+z| x, y, z are binary integers, and x is the sum of y and z}.

Show that ADD is not regular.

1.54 Consider the language F = {ai bj ck | i, j, k ≥ 0 and if i = 1 then j = k}.

a. Show that F is not regular.

b. Show that F acts like a regular language in the pumping lemma. In other
words, give a pumping length p and demonstrate that F satisfies the three
conditions of the pumping lemma for this value of p.
c. Explain why parts (a) and (b) do not contradict the pumping lemma.

1.55 The pumping lemma says that every regular language has a pumping length p, such
that every string in the language can be pumped if it has length p or more. If p is a
pumping length for language A, so is any length p0 ≥ p. The minimum pumping
length for A is the smallest p that is a pumping length for A. For example, if
A = 01∗ , the minimum pumping length is 2. The reason is that the string s = 0 is
in A and has length 1 yet s cannot be pumped; but any string in A of length 2 or
more contains a 1 and hence can be pumped by dividing it so that x = 0, y = 1,
and z is the rest. For each of the following languages, give the minimum pumping
length and justify your answer.
A
a. 0001∗ f. ε
A
b. 0∗ 1∗ g. 1∗ 01∗ 01∗
c. 001 ∪ 0∗ 1∗ h. 10(11∗ 0)∗ 0
A
d. 0∗ 1+ 0+ 1∗ ∪ 10∗ 1 i. 1011
e. (01)∗ j. Σ∗

?
1.56 If A is a set of natural numbers and k is a natural number greater than 1, let

Bk (A) = {w| w is the representation in base k of some number in A}.

Here, we do not allow leading 0s in the representation of a number. For example,

B2 ({3, 5}) = {11, 101} and B3 ({3, 5}) = {10, 12}. Give an example of a set A for
which B2 (A) is regular but B3 (A) is not regular. Prove that your example works.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 92 CHAPTER 1 / REGULAR LANGUAGES

?
1.57 If A is any language, let A 1 − be the set of all first halves of strings in A so that
2

A 1 − = {x| for some y, |x| = |y| and xy ∈ A}.

2

Show that if A is regular, then so is A 1 − .

2
?
1.58 If A is any language, let A 1 − 1 be the set of all strings in A with their middle thirds
3 3
removed so that

A 1 − 1 = {xz| for some y, |x| = |y| = |z| and xyz ∈ A}.

3 3

Show that if A is regular, then A 1 − 1 is not necessarily regular.

3 3
?
1.59 Let M = (Q, Σ, δ, q0 , F ) be a DFA and let h be a state of M called its “home”.
A synchronizing sequence for M and h is a string s ∈ Σ∗ where δ(q, s) = h for
every q ∈ Q. (Here we have extended δ to strings, so that δ(q, s) equals the state
where M ends up when M starts at state q and reads input s.) Say that M is
synchronizable if it has a synchronizing sequence for some state h. Prove that if M
is a k-state synchronizable DFA, then it has a synchronizing sequence of length at
most k3 . Can you improve upon this bound?
1.60 Let Σ = {a, b}. For each k ≥ 1, let Ck be the language consisting of all strings
that contain an a exactly k places from the right-hand end. Thus Ck = Σ∗ aΣk−1 .
Describe an NFA with k + 1 states that recognizes Ck in terms of both a state
diagram and a formal description.
1.61 Consider the languages Ck defined in Problem 1.60. Prove that for each k, no DFA
can recognize Ck with fewer than 2k states.
1.62 Let Σ = {a, b}. For each k ≥ 1, let Dk be the language consisting of all strings
that have at least one a among the last k symbols. Thus Dk = Σ∗ a(Σ ∪ ε)k−1 .
Describe a DFA with at most k + 1 states that recognizes Dk in terms of both a state
diagram and a formal description.
?
1.63 a. Let A be an infinite regular language. Prove that A can be split into two
infinite disjoint regular subsets.
b. Let B and D be two languages. Write B b D if B ⊆ D and D contains
infinitely many strings that are not in B. Show that if B and D are two
regular languages where B b D, then we can find a regular language C
where B b C b D.
1.64 Let N be an NFA with k states that recognizes some language A.
a. Show that if A is nonempty, A contains some string of length at most k.
b. Show, by giving an example, that part (a) is not necessarily true if you replace
both A’s by A.
c. Show that if A is nonempty, A contains some string of length at most 2k .
d. Show that the bound given in part (c) is nearly tight; that is, for each k,
demonstrate an NFA recognizing a language Ak where Ak is nonempty and
where Ak ’s shortest member strings are of length exponential in k. Come as
close to the bound in (c) as you can.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 PROBLEMS 93

?
1.65 Prove that for each n > 0, a language Bn exists where
a. Bn is recognizable by an NFA that has n states, and
b. if Bn = A1 ∪ · · · ∪ Ak , for regular languages Ai , then at least one of the Ai
requires a DFA with exponentially many states.
1.66 A homomorphism is a function f : Σ−→Γ∗ from one alphabet to strings over
another alphabet. We can extend f to operate on strings by defining f (w) =
f (w1 )f (w2 ) · · · f (wn ), where w = w1 w2 · · · wn and each wi ∈ Σ. We further
extend f to operate on languages by defining f (A) = {f (w)| w ∈ A}, for any
language A.
a. Show, by giving a formal construction, that the class of regular languages
is closed under homomorphism. In other words, given a DFA M that rec-
ognizes B and a homomorphism f , construct a finite automaton M 0 that
recognizes f (B). Consider the machine M 0 that you constructed. Is it a
DFA in every case?
b. Show, by giving an example, that the class of non-regular languages is not
closed under homomorphism.
?
1.67 Let the rotational closure of language A be RC(A) = {yx| xy ∈ A}.
a. Show that for any language A, we have RC(A) = RC(RC(A)).
b. Show that the class of regular languages is closed under rotational closure.
?
1.68 In the traditional method for cutting a deck of playing cards, the deck is arbitrarily
split two parts, which are exchanged before reassembling the deck. In a more
complex cut, called Scarne’s cut, the deck is broken into three parts and the middle
part in placed first in the reassembly. We’ll take Scarne’s cut as the inspiration for
an operation on languages. For a language A, let CUT(A) = {yxz| xyz ∈ A}.
a. Exhibit a language B for which CUT(B) 6= CUT(CUT(B)).
b. Show that the class of regular languages is closed under CUT.

1.69 Let Σ = {0,1}. Let WWk = {ww| w ∈ Σ∗ and w is of length k}.

a. Show that for each k, no DFA can recognize WWk with fewer than 2k states.
b. Describe a much smaller NFA for WWk , the complement of WWk .
1.70 We define the avoids operation for languages A and B to be

A avoids B = {w| w ∈ A and w doesn’t contain any string in B as a substring}.

Prove that the class of regular languages is closed under the avoids operation.
1.71 Let Σ = {0,1}.
a. Let A = {0k u0k | k ≥ 1 and u ∈ Σ∗ }. Show that A is regular.
b. Let B = {0k 1u0k | k ≥ 1 and u ∈ Σ∗ }. Show that B is not regular.
1.72 Let M1 and M2 be DFAs that have k1 and k2 states, respectively, and then let
U = L(M1 ) ∪ L(M2 ).
a. Show that if U 6= ∅, then U contains some string s, where |s| < max(k1 , k2 ).
b. Show that if U 6= Σ∗ , then U excludes some string s, where |s| < k1 k2 .
1.73 Let Σ = {0,1, #}. Let C = {x#xR #x| x ∈ {0,1}∗ }. Show that C is a CFL.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 94 CHAPTER 1 / REGULAR LANGUAGES

SELECTED SOLUTIONS
1.1 For M1 : (a) q1 ; (b) {q2 }; (c) q1 , q2 , q3 , q1 , q1 ; (d) No; (e) No
For M2 : (a) q1 ; (b) {q1 , q4 }; (c) q1 , q1 , q1 , q2 , q4 ; (d) Yes; (e) Yes

1.2 M1 = ({q1 , q2 , q3 }, {a, b}, δ1 , q1 , {q2 }).

M2 = ({q1 , q2 , q3 , q4 }, {a, b}, δ2 , q1 , {q1 , q4 }).
The transition functions are

δ1 a b δ2 a b
q1 q2 q1 q1 q1 q2
q2 q3 q3 q2 q3 q4
q3 q2 q1 q3 q2 q1
q4 q3 q4 .

1.4 (b) The following are DFAs for the two languages {w| w has exactly two a’s} and
{w| w has at least two b’s}.

a a a,b
b b

Combining them using the intersection construction gives the following DFA.

Though the problem doesn’t request you to simplify the DFA, certain states can be
combined to give the following DFA.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 SELECTED SOLUTIONS 95

(d) These are DFAs for the two languages {w| w has an even number of a’s} and
{w| each a in w is followed by at least one b}.

Combining them using the intersection construction gives the following DFA.

Though the problem doesn’t request you to simplify the DFA, certain states can be
combined to give the following DFA.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 96 CHAPTER 1 / REGULAR LANGUAGES

1.5 (a) The left-hand DFA recognizes {w| w contains ab}. The right-hand DFA recog-
nizes its complement, {w| w doesn’t contain ab}.

(b) This DFA recognizes {w| w contains baba}.

This DFA recognizes {w| w does not contain baba}.

1.7 (a) (f)

1.11 Let N = (Q, Σ, δ, q0 , F ) be any NFA. Construct an NFA N 0 with a single accept
state that recognizes the same language as N . Informally, N 0 is exactly like N
except it has ε-transitions from the states corresponding to the accept states of
N , to a new accept state, qaccept . State qaccept has no emerging transitions. More
formally, N 0 = (Q ∪ {qaccept }, Σ, δ 0 , q0 , {qaccept }), where for each q ∈ Q and a ∈ Σε
(
0 δ(q, a) if a 6= ε or q 6∈ F
δ (q, a) =
δ(q, a) ∪ {qaccept } if a = ε and q ∈ F

and δ 0 (qaccept , a) = ∅ for each a ∈ Σε .

1.23 We prove both directions of the “iff.”

(→) Assume that B = B + and show that BB ⊆ B.
For every language BB ⊆ B + holds, so if B = B + , then BB ⊆ B.
(←) Assume that BB ⊆ B and show that B = B + .
For every language B ⊆ B + , so we need to show only B + ⊆ B. If w ∈ B + ,
then w = x1 x2 · · · xk where each xi ∈ B and k ≥ 1. Because x1 , x2 ∈ B and
BB ⊆ B, we have x1 x2 ∈ B. Similarly, because x1 x2 is in B and x3 is in B, we
have x1 x2 x3 ∈ B. Continuing in this way, x1 · · · xk ∈ B. Hence w ∈ B, and so
we may conclude that B + ⊆ B.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 SELECTED SOLUTIONS 97

The latter argument may be written formally as the following proof by induction.
Assume that BB ⊆ B.
Claim: For each k ≥ 1, if x1 , . . . , xk ∈ B, then x1 · · · xk ∈ B.
Basis: Prove for k = 1. This statement is obviously true.
Induction step: For each k ≥ 1, assume that the claim is true for k and prove it to be
true for k + 1.
If x1 , . . . , xk , xk+1 ∈ B, then by the induction assumption, x1 · · · xk ∈ B. There-
fore, x1 · · · xk xk+1 ∈ BB, but BB ⊆ B, so x1 · · · xk+1 ∈ B. That proves the
induction step and the claim. The claim implies that if BB ⊆ B, then B + ⊆ B.

1.29 (a) Assume that A1 = {0n 1n 2n | n ≥ 0} is regular. Let p be the pumping length
given by the pumping lemma. Choose s to be the string 0p 1p 2p . Because s is a
member of A1 and s is longer than p, the pumping lemma guarantees that s can
be split into three pieces, s = xyz, where for any i ≥ 0 the string xy i z is in A1 .
Consider two possibilities:

1. The string y consists only of 0s, only of 1s, or only of 2s. In these cases, the
string xyyz will not have equal numbers of 0s, 1s, and 2s. Hence xyyz is not
a member of A1 , a contradiction.
2. The string y consists of more than one kind of symbol. In this case, xyyz
will have the 0s, 1s, or 2s out of order. Hence xyyz is not a member of A1 ,
a contradiction.

Either way we arrive at a contradiction. Therefore, A1 is not regular.

n
(c) Assume that A3 = {a2 | n ≥ 0} is regular. Let p be the pumping length given
p
by the pumping lemma. Choose s to be the string a2 . Because s is a member of
A3 and s is longer than p, the pumping lemma guarantees that s can be split into
three pieces, s = xyz, satisfying the three conditions of the pumping lemma.

The third condition tells us that |xy| ≤ p. Furthermore, p < 2p and so |y| < 2p .
Therefore, |xyyz| = |xyz| + |y| < 2p + 2p = 2p+1 . The second condition requires
|y| > 0 so 2p < |xyyz| < 2p+1 . The length of xyyz cannot be a power of 2. Hence
xyyz is not a member of A3 , a contradiction. Therefore, A3 is not regular.

1.40 (a) Let M = (Q, Σ, δ, q0 , F ) be a DFA recognizing A, where A is some regular

language. Construct M 0 = (Q0 , Σ, δ 0 , q0 0 , F 0 ) recognizing NOPREFIX (A) as
follows:

1. Q0 = Q. (
0 0 {δ(r, a)} if r ∈
/F
2. For r ∈ Q and a ∈ Σ, define δ (r, a) =
∅ if r ∈ F.
3. q0 0 = q0 .
4. F 0 = F .

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 98 CHAPTER 1 / REGULAR LANGUAGES

1.44 Let MB = (QB , Σ, δB , qB , FB ) and MC = (QC , Σ, δC , qC , FC ) be DFAs recog-

nizing B and C, respectively. Construct NFA M = (Q, Σ, δ, q0 , F ) that recognizes
1 1
B ← C as follows. To decide whether its input w is in B ← C, the machine
M checks that w ∈ B, and in parallel nondeterministically guesses a string y that
contains the same number of 1s as contained in w and checks that y ∈ C.
1. Q = QB × QC .
2. For (q, r) ∈ Q and a ∈ Σε , define

{(δB (q, 0), r)}
 if a = 0
δ((q, r), a) = {(δB (q, 1), δC (r, 1))} if a = 1

{(q, δC (r, 0))} if a = ε.


3. q0 = (qB , qC ).
4. F = FB × FC .
1.46 (b) Let B = {0m 1n | m 6= n}. Observe that B ∩ 0∗ 1∗ = {0k 1k | k ≥ 0}. If B were
regular, then B would be regular and so would B ∩ 0∗ 1∗ . But we already know that
{0k 1k | k ≥ 0} isn’t regular, so B cannot be regular.
Alternatively, we can prove B to be nonregular by using the pumping lemma di-
rectly, though doing so is trickier. Assume that B = {0m 1n | m 6= n} is regular.
Let p be the pumping length given by the pumping lemma. Observe that p! is di-
visible by all integers from 1 to p, where p! = p(p − 1)(p − 2) · · · 1. The string
s = 0p 1p+p! ∈ B, and |s| ≥ p. Thus the pumping lemma implies that s can be di-
vided as xyz with x = 0a , y = 0b , and z = 0c 1p+p! , where b ≥ 1 and a + b + c = p.
Let s0 be the string xy i+1 z, where i = p!/b. Then y i = 0p! so y i+1 = 0b+p! , and
so s0 = 0a+b+c+p! 1p+p! . That gives s0 = 0p+p! 1p+p! 6∈ B, a contradiction.
1.50 Assume to the contrary that some FST T outputs wR on input w. Consider the
input strings 00 and 01. On input 00, T must output 00, and on input 01, T must
output 10. In both cases, the first input bit is a 0 but the first output bits differ.
Operating in this way is impossible for an FST because it produces its first output
bit before it reads its second input. Hence no such FST can exist.
1.52 (a) We prove this assertion by contradiction. Let M be a k-state DFA that recog-
nizes L. Suppose for a contradiction that L has index greater than k. That means
some set X with more than k elements is pairwise distinguishable by L. Because M
has k states, the pigeonhole principle implies that X contains two distinct strings x
and y, where δ(q0 , x) = δ(q0 , y). Here δ(q0 , x) is the state that M is in after start-
ing in the start state q0 and reading input string x. Then, for any string z ∈ Σ∗ ,
δ(q0 , xz) = δ(q0 , yz). Therefore, either both xz and yz are in L or neither are
in L. But then x and y aren’t distinguishable by L, contradicting our assumption
that X is pairwise distinguishable by L.
(b) Let X = {s1 , . . . , sk } be pairwise distinguishable by L. We construct DFA
M = (Q, Σ, δ, q0 , F ) with k states recognizing L. Let Q = {q1 , . . . , qk }, and
define δ(qi , a) to be qj , where sj ≡L si a (the relation ≡L is defined in Prob-
lem 1.51). Note that sj ≡L si a for some sj ∈ X; otherwise, X ∪ si a would have
k + 1 elements and would be pairwise distinguishable by L, which would contra-
dict the assumption that L has index k. Let F = {qi | si ∈ L}. Let the start
state q0 be the qi such that si ≡L ε. M is constructed so that for any state qi ,
{s| δ(q0 , s) = qi } = {s| s ≡L si }. Hence M recognizes L.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
 SELECTED SOLUTIONS 99

(c) Suppose that L is regular and let k be the number of states in a DFA recognizing
L. Then from part (a), L has index at most k. Conversely, if L has index k, then
by part (b) it is recognized by a DFA with k states and thus is regular. To show that
the index of L is the size of the smallest DFA accepting it, suppose that L’s index
is exactly k. Then, by part (b), there is a k-state DFA accepting L. That is the
smallest such DFA because if it were any smaller, then we could show by part (a)
that the index of L is less than k.
1.55 (a) The minimum pumping length is 4. The string 000 is in the language but
cannot be pumped, so 3 is not a pumping length for this language. If s has length
4 or more, it contains 1s. By dividing s into xyz, where x is 000 and y is the first 1
and z is everything afterward, we satisfy the pumping lemma’s three conditions.
(b) The minimum pumping length is 1. The pumping length cannot be 0 because
the string ε is in the language and it cannot be pumped. Every nonempty string in
the language can be divided into xyz, where x, y, and z are ε, the first character,
and the remainder, respectively. This division satisfies the three conditions.
(d) The minimum pumping length is 3. The pumping length cannot be 2 because
the string 11 is in the language and it cannot be pumped. Let s be a string in the
language of length at least 3. If s is generated by 0∗ 1+ 0+ 1∗ and s begins either 0
or 11, write s = xyz where x = ε, y is the first symbol, and z is the remainder of
s. If s is generated by 0∗ 1+ 0+ 1∗ and s begins 10, write s = xyz where x = 10, y is
the next symbol, and z is the remainder of s. Breaking s up in this way shows that
it can be pumped. If s is generated by 10∗ 1, we can write it as xyz where x = 1,
y = 0, and z is the remainder of s. This division gives a way to pump s.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.