Information Technology Reference
In-Depth Information
1
Start
q
0
q
1
1
0
0
0
0
1
q
2
q
3
1
Figure 4.1
The deterministic finite-state machines
M
odd
/
even
that accepts strings containing
an odd number of 0's and an even number of 1's.
Figure
4.1
shows a DFSM
M
odd
/
even
with initial state
q
0
. The final state is shown as
a shaded circle; that is,
F
=
.
M
odd
/
even
is in state
q
0
or
q
2
as long as the number
of 1's in its input is even and is in state
q
1
or
q
3
as long as the number of 1's in its input is
odd. Similarly,
M
odd
/
even
is in state
q
0
or
q
1
as long as the number of 0's in its input is even
and is in states
q
2
or
q
3
as long as the number of 0's in its input is odd. Thus,
M
odd
/
even
recognizes the language of binary strings containing an odd number of 0's and an even number
of 1's.
When the next-set function
δ
for an NFSM has value
δ
(
q
,
a
)=
{
q
2
}
, the empty set, for
state-input pair
(
q
,
a
)
, no transition is specified from state
q
on input letter
a
.
Figure
4.2
shows a simple NFSM ND with initial state
q
0
and final state set
F
=
∅
{
q
0
,
q
3
,
q
5
. Nondeterministic transitions are possible from states
q
0
,
q
3
,and
q
5
. In addition, no
transition is specified on input 0 from states
q
1
and
q
2
nor on input 1 from states
q
0
,
q
3
,
q
4
,
or
q
5
.
}
0
1
q
1
q
3
0
Start
0
q
0
0
0
1
0
q
2
q
4
q
5
0
Figure 4.2
The nondeterministic machine ND.
Search WWH ::
Custom Search