CSI 409 — Spring 2021: Midterm Exam
Some answers and hints
1. (This question has 3 parts.)
The alphabet is {a,b} in all cases.
(a) Design a DFA for the language a∗b∗.
b
a
1 2 3
a
b a, b
(b) Design a DFA for the language
{
w ∈ {a,b}∗
∣∣ |w| is an odd number
}
C
a,b
D
a,b
1 see next page
(c) Use the product construction method to design a DFA for the language
{
aib j
∣∣ i+ j is an odd number
}
a, b
1,C 3,C
3,D1,D
2,D
2,C
a a b b
b a
b a
a, b
2 see next page
2. Exhibit a string over the alphabet {a,b} that does not belong to (a∪ba)∗(b∪ab)∗.
Justify your answer. (No formal proof is needed.)
Hint: You may want to construct an NFA for this regular expression.
bba: bba does not belong to (a∪ba)∗ or (b∪ab)∗. Besides, no nonempty prefix of bba
belongs to (a∪ba)∗.
Alternatively, here is an NFA for (a∪ba)∗(b∪ab)∗:
4
a
b a
ε
2
1 3
b
ba
There is no legal accepting trace for bba.
3 see next page
3. Consider the following NFA. The set of states, Q, is {1,2,3}. The initial state is 1 and the ac-
cepting state is 3. The alphabet is {a,b}.
a,
1 2
a, b
3
b ε
Convert this NFA to a DFA using the subset construction method taught in class. Show work
clearly.
a
1 1,2,3
1,3
a
a
b
b
b
4 see next page
4. Derive a regular expression using the algebraic method for the language recognized by the fol-
lowing DFA:
b
3
1 2

4
a
a,b
a
b b
a
The equations are
X1 = aX3 ∪ bX2 (1)
X2 = aX1 ∪ bX2 (2)
X3 = aX3 ∪ bX4 ∪ ε (3)
X4 = aX4 ∪ bX4 (4)
Clearly X4 = /0. Thus X3 = aX3 ∪ ε and, by Arden’s Lemma, X3 = a
∗. Replacing X3 in (1),
we get X1 = a
+ ∪ bX2. We can apply Arden’s Lemma to (2) to get X2 = b
∗aX1. Thus we
finally get
X1 = a
+ ∪ b+aX1
Applying Arden’s Lemma again, we get
X1 =
(
b+a
)∗
a+
Alternatively, you can use (1) and (2) to get
X2 =
(
b ∪ ab)∗aaX3
1Arden’s Lemma: An equation of the form X = AX ∪B, where ε 6∈ A, has unique solution X = A∗B
5 see next page
Since X3 = a
∗, X2 =
(
b ∪ ab)∗aaa∗. Now (1) gives us the final answer:
a+ ∪ b
(
b ∪ ab)∗aaa∗
6

欢迎咨询51作业君