(b)
(c)
28. (a) A 1 followed by any number of 0s
(b) Any number of copies of 10, including null string
(c) The string 0 or the string 01
(d) Any string beginning with 0.
(e) Any string not ending with 0.
29.
30. G = (V, T, S, P)
G S A B
= { , , , , }
01
T = { , }
0 1
S
A S
B S
A
A A
B
A
B
A B
B B
→
→
→
→
→
→
→
→
→
0
1
0
1
1
0
1
1
,
,
,
,
,
,
,
,
.
λ
32. (a) 00 1
*
(b) (
) (
) (
)
*
*
0 1 0 1 0 1 0000
∪
∪
∪
34.
Answers to Exercises
313
s 0
s 1
1
Start
0,1
0
s 4
s 2
1
s 3
0,1
0
0,1
s 0
s 1
0
Start
0,1
1
s 2
0,1
s 0
s 2
0
Start
s 1
1
1
s 0
s 2
Start
s 1
0
s 3
s 4
s 5
0
0
0
1
1
1
0
0