39. (a ∪ b)* aba
CHAPTER 2
3.
5.
7. Let S A and S B be the start symbols of G A and G B respectively. Let S be a
new start symbol.
(a) Add S and productions S
S A
→
and S
S B
→
(b) Add S and production S
S S
A B
→
(c) Add S and production S → λ and S
S S
A
→
.
8. (a) Type 2, not type 3
(b) Type 0, not type 1
(c) Type 2
(d) Type 3
(e) Type 2, not type 3
Answers to Exercises
315
S
S
S
S
S S
S
a
b a
+
*
*
b
a
a
x 0
b
c
b
x 0
x 0
x 1
x 1
a
ε
ε
b
ε
ε
ε
ε
ε
ε
ε
ε
b
a
a
CHAPTER 2
3.
5.
7. Let S A and S B be the start symbols of G A and G B respectively. Let S be a
new start symbol.
(a) Add S and productions S
S A
→
and S
S B
→
(b) Add S and production S
S S
A B
→
(c) Add S and production S → λ and S
S S
A
→
.
8. (a) Type 2, not type 3
(b) Type 0, not type 1
(c) Type 2
(d) Type 3
(e) Type 2, not type 3
Answers to Exercises
315
S
S
S
S
S S
S
a
b a
+
*
*
b
a
a
x 0
b
c
b
x 0
x 0
x 1
x 1
a
ε
ε
b
ε
ε
ε
ε
ε
ε
ε
ε
b
a
a