756
Modeling Arithmetic, Computation, and Languages
For Exercises 39–42, give a regular expression for the set recognized by the finite-state machine.
39. present state
next state
output
present input
0
1
s 0
s 3
s 1
0
s 1
s 1
s 2
0
s 2
s 3
s 3
1
s 3
s 3
s 3
0
40. present state
next state
output
present input
0
1
s 0
s 3
s 1
1
s 1
s 1
s 2
1
s 2
s 2
s 2
0
s 3
s 0
s 2
0
41. present state
next state
output
present input
0
1
s 0
s 2
s 1
1
s 1
s 3
s 1
1
s 2
s 3
s 4
0
s 3
s 3
s 3
0
s 4
s 5
s 3
0
s 5
s 2
s 3
1
42. present state
next state
output
present input
0
1
s 0
s 4
s 1
1
s 1
s 4
s 2
0
s 2
s 4
s 3
0
s 3
s 3
s 1
1
s 4
s 4
s 4
0
43. Give a regular expression for each of the following sets.
a. set of all strings of 0s and 1s beginning with 0 and ending with 1
b. set of all strings of 0s and 1s having an odd number of 0s
c. 5101, 1001, 10001, 100001, …6
44. Give a regular expression for each of the following sets.
a. set of all strings of 0s and 1s containing at least one 0
b. set of all strings of a’s and b’s where each a is followed by two b’s
c. set of all strings of 0s and 1s containing exactly two 0s
38.
s 0
s 2
1
1
s 1
0
0
0
1
37.
s 0
s 1
0
0
0
1
1
1
0,1
s 3
s 2