Section 9.4 Turing Machines
759
71. present state
next state
output
present input
a
b
c
0
1
4
0
1
1
4
2
3
0
2
3
4
2
1
3
4
0
1
0
4
1
0
2
0
72. present state
next state
output
present input
0
1
0
1
3
1
1
2
0
0
2
4
3
1
3
0
1
1
4
2
4
0
73. present state
next state
output
present input
0
1
0
3
0
0
1
4
3
1
2
1
4
0
3
0
4
1
4
5
2
0
5
2
3
1
74. present state
next state
output
present input
0
1
0
3
5
1
1
1
6
1
2
0
4
0
3
1
6
1
4
5
3
0
5
4
1
0
6
2
5
1
75. Construct a sequential network for the finite-state machine of Exercise 8.
76. Construct a sequential network for the finite-state machine of Exercise 1a. Make use of don’t-care conditions to simplify the network.
S e c t i o n 9 . 4 turing MAChineS
In Section 9.3, we noted that because S = 50
n
1
n
0 n ≥ 06 is not a regular set,
Kleene’s theorem tells us that it is not recognizable by any finite-state machine.
We didn’t actually prove that S is not a regular set, however; we only noted that
we were not able to come up with a regular expression for it. Let’s take a slightly
different approach.
Suppose S is recognized by a finite-state machine M with m states. Then all
strings from S and only strings from S lead M from its start state to a final state.
Now let us run M a number of times on successive input strings of l, 0, 0
2
, 0
3
… , 0
m
.
At the end of processing each of these m + 1 strings, M will be in some state.
Because M has only m distinct states, there must be two strings from this list,
say 0
v
and 0
w
, v ∙ w, each of which lead M from the start state to the same state.
(This is actually a result of the pigeonhole principle of Chapter 4, where the items
are the input strings and the bins into which we put the items are the states M is
in after processing the strings.) Because M recognizes S, the input string 0
v
1
v
will
cause M to end in a final state. But because M is in the same state after processing
0
w
as after processing 0
v
, the string 0
w
1
v
, which does not belong to S, will take M
to the same final state. This contradiction proves that no finite-state machine can
recognize S.
759
71. present state
next state
output
present input
a
b
c
0
1
4
0
1
1
4
2
3
0
2
3
4
2
1
3
4
0
1
0
4
1
0
2
0
72. present state
next state
output
present input
0
1
0
1
3
1
1
2
0
0
2
4
3
1
3
0
1
1
4
2
4
0
73. present state
next state
output
present input
0
1
0
3
0
0
1
4
3
1
2
1
4
0
3
0
4
1
4
5
2
0
5
2
3
1
74. present state
next state
output
present input
0
1
0
3
5
1
1
1
6
1
2
0
4
0
3
1
6
1
4
5
3
0
5
4
1
0
6
2
5
1
75. Construct a sequential network for the finite-state machine of Exercise 8.
76. Construct a sequential network for the finite-state machine of Exercise 1a. Make use of don’t-care conditions to simplify the network.
S e c t i o n 9 . 4 turing MAChineS
In Section 9.3, we noted that because S = 50
n
1
n
0 n ≥ 06 is not a regular set,
Kleene’s theorem tells us that it is not recognizable by any finite-state machine.
We didn’t actually prove that S is not a regular set, however; we only noted that
we were not able to come up with a regular expression for it. Let’s take a slightly
different approach.
Suppose S is recognized by a finite-state machine M with m states. Then all
strings from S and only strings from S lead M from its start state to a final state.
Now let us run M a number of times on successive input strings of l, 0, 0
2
, 0
3
… , 0
m
.
At the end of processing each of these m + 1 strings, M will be in some state.
Because M has only m distinct states, there must be two strings from this list,
say 0
v
and 0
w
, v ∙ w, each of which lead M from the start state to the same state.
(This is actually a result of the pigeonhole principle of Chapter 4, where the items
are the input strings and the bins into which we put the items are the states M is
in after processing the strings.) Because M recognizes S, the input string 0
v
1
v
will
cause M to end in a final state. But because M is in the same state after processing
0
w
as after processing 0
v
, the string 0
w
1
v
, which does not belong to S, will take M
to the same final state. This contradiction proves that no finite-state machine can
recognize S.