Information Technology Reference
In-Depth Information
x
y
y
q
1
s
1
f
1
x
x
y
s
0
Figure 4.9
Amachine
M
accepts
r
1
.
M
1
accepts
r
1
.Make
s
0
the initial state of
M
.For
each input letter
a
, add an edge labeled
a
from
s
0
and each final of
M
1
to each state reached on
input
a
from
s
1
, the initial state of
M
1
. The final states of
M
are
s
0
and the final states of
M
1
.
Thus,
M
accepts
and all states reached by the concatenation of strings accepted by
M
1
;thatis,
it realizes the closure
r
1
.
Start
0
Start
1
s
1
q
1
s
2
q
2
(a)
(b)
Figure 4.10
Nondeterministic machines accepting 0 and 1.
0
0
q
1
s
1
0
Start
s
0
Figure 4.11
An NFSM accepting the Kleene closure of
{
}
0
.
0
Start
1
0
s
2
q
2
q
1
s
1
0
Figure 4.12
A nondeterministic machine accepting 10
∗
.
Search WWH ::
Custom Search