Java Reference
In-Depth Information
27. Let
F
be any NFA that contains
transitions. Write an algorithm that
transforms
F
into an equivalent NFA
F
that contains no
λ
transitions.
Note
: You need not use the subset construction, since you are creating an
NFA, not a DFA.
λ
28. Let
s
be a string. Define
Insert
(
s
) to be the function that inserts a # into
each possible position in
s
.If
s
is
n
characters long, then
Insert
(
s
) returns
asetof
n
+
1 strings (since there are
n
+
1 places, a # may be inserted in a
string of length
n
).
For example,
Insert
(
abc
)
={
#
abc
,
a
#
bc
,
ab
#
c
,
abc
#
}
.
Insert
applied to a set
of strings is the union of
Insert
applied to members of the set. Thus,
Insert
(
ab
,
de
)
.
Let
R
be any regular set. Show that
Insert
(
R
) is a regular set.
Hint
:GivenanFAfor
R
, construct one for
Insert
(
R
).
={
#
ab
,
a
#
b
,
ab
#
,
#
de
,
d
#
e
,
de
#
}
29. Let
D
be any deterministic finite automaton. Assume that you know
D
contains exactly
n
states and that it accepts at least one string of length
n
or greater. Show that
D
must also accept at least one string of length 2
n
or greater.
