Information Technology Reference
In-Depth Information
b) Convert the nondeterministic finite-state machine of part (a) to a deterministic
finite-state machine by the method of Section
4.2
.
4.15 Describe an algorithm to convert a regular expression to an NFSM using the proof of
Theorem
4.4.1
.
4.16 Design DFSMs that recognize the following languages:
a)
a
∗
bca
∗
b)
(
a
+
c
)
∗
(
ab
+
ca
)
b
∗
c)
(
a
∗
b
∗
(
b
+
c
)
∗
)
∗
4.17 Design an FSM that recognizes decimal strings (over the alphabet
{
0, 1, 2, 3, 4, 5, 6,
7, 8, 9
representing the integers whose value is 0 modulo 3.
Hint:
Use the fact that
(
10
)
k
=
1
mod
3 (where 10 is “ten”) to show that
(
a
k
(
10
)
k
+
a
k−
1
(
10
)
k−
1
+
}
+
a
1
(
10
)
1
+
a
0
)mod
3
=(
a
k
+
a
k−
1
+
+
a
1
+
a
0
)mod
3.
4.18 Use the above FSM design to generate a regular expression describing those integers
whose value is 0 modulo 3.
4.19 Describe an algorithm that constructs an NFSM from a regular expression
r
and accepts
astring
w
if
w
contains a string denoted by
r
that begins anywhere in
w
.
···
···
THE PUMPING LEMMA
4.20 Show that the following languages are not regular:
a)
a
n
ba
n
L
=
{
|
n
≥
}
0
0
n
1
2
n
0
n
L
=
{
|
n
≥
}
b)
1
a
n
b
n
c
n
}
4.21 Strengthen the pumping lemma for regular languages by demonstrating that if
L
is
a regular language over the alphabet
Σ
recognized by a DFSM with
m
states and it
contains a string
w
of length
m
or more, then any substring
z
of
w
(
w
=
uzv
)of
length
m
can be written as
z
=
rst
,where
c)
L
=
{
|
n
≥
0
|
s
|≥
1 such that for all integers
n
≥
0,
urs
n
tv
L
. Explain why this pumping lemma is stronger than the one stated in
Lemma
4.5.1
.
4.22 Show that the language
L
=
∈
a
i
b
j
is not regular.
4.23 Show that the following language is not regular:
a)
{
|
i>j
}
u
n
zv
m
zw
n
+
m
{
|
n
,
m
≥
}
1
PROPERTIES OF REGULAR LANGUAGES
4.24 Use Lemma
4.5.1
and the closure property of regular languages under intersection to
show that the following languages are not regular:
a)
ww
R
}
∗
}
{
|
w
∈{
0, 1
b)
{
ww
|
where
w
denotes
w
in which 0's and 1's are interchanged
}
}
4.25 Prove or disprove each of the following statements:
a) Every subset of a regular language is regular
c)
{
w
|
w
has equal number of 0's and 1's
Search WWH ::
Custom Search