Information Technology Reference
In-Depth Information
0
0
1
Start
q
0
q
1
1
0
0, 1
1
0, 1
0
q
2
q
3
Figure 4.32
A nondeterministic FSM.
L
=
{
w
|
w
has length at least 3 and its third symbol is a 0
}
a)
L
=
{
w
|
w
begins with a 1 and ends with a 0
}
b)
}
4.9 Give regular expressions generating the following languages over
Σ=
c)
L
=
{
w
|
w
contains at least three 1s
{
0, 1
}
:
a)
L
=
{
w
|
w
is any string except 11 and 111
}
}
4.10 Give regular expressions for the languages over the alphabet
L
=
{
w
|
every odd position of
w
is a 1
b)
{
0, 1, 2, 3, 4, 5, 6, 7, 8,
}
describing positive integers that are:
a) even
b) odd
c) a multiple of 5
d) a multiple of 4
4.11 Give proofs for the rules stated in Theorem
4.3.1
.
4.12 Show that
+
01
+(
010
)(
10
+
010
)
∗
(
+
1
+
01
)
and
(
01
+
010
)
∗
describe the same
language.
9
REGULAR EXPRESSIONS AND FSMS
4.13 a) Find a simple nondeterministic finite-state machine accepting the language
(
01
∪
010
)
∗
over
Σ=
∪
{
}
.
b) Convert the nondeterministic finite state machine of part (a) to a deterministic
finite-state machine by the method of Section
4.2
.
4.14 a) Let
Σ=
001
0, 1
,andlet
L
be the language over
Σ
that contains each string
w
ending with some symbol that does not occur anywhere else in
w
.Forexam-
ple, 011012, 20021, 11120, 0002, 10, and 1 are all strings in
L
.Constructa
nondeterministic finite-state machine that accepts
L
.
{
0, 1, 2
}
Search WWH ::
Custom Search