Information Technology Reference
In-Depth Information
(
1
)
r
∅
=
∅
r
=
∅
(
2
)
r
=
r
=
r
(
3
)
r
+
∅
=
∅
+
r
=
r
(
4
)
r
+
r
=
r
(
5
)
r
+
s
=
s
+
r
(
6
)
r
(
s
+
t
)
=
rs
+
rt
(
7
)
r
+
s
)
t
=
rt
+
st
r
(
st
)
=(
rs
)
t
(
8
)
∅
∗
(
9
)
=
∗
(
10
)
=
r
∗
(
11
)(
+
r
)
+
=
(
12
)(
+
r
)
∗
r
∗
=
r
∗
(
+
r
)=(
+
r
)
r
∗
r
∗
(
13
)
=
r
∗
s
+
s
r
∗
s
(
14
)
=
r
(
sr
)
∗
=
rs
)
∗
r
(
15
)
(
16
)
r
+
s
)
∗
=
r
∗
s
)
∗
r
∗
=
s
∗
r
)
∗
s
∗
Figure 4.5
Rules that apply to regular expressions.
wherewehavesimplifiedtheexpressionsusingthedefinitionofthepositiveclosure,namely
r
(
r
∗
)=
r
+
in the second equation and rules (6), (5), and (12) in the last three equations.
Other examples of the use of the identities can be found in Section
4.4
.
4.4 Regular Expressions and FSMs
Regular languages are exactly the languages recognized by finite-state machines, as we now
show. Our two-part proof begins by showing (Section
4.4.1
) that every regular language can
be accepted by a nondeterministic finite-state machine. This is followed in Section
4.4.2
by
a proof that the language recognized by an arbitrary deterministic finite-state machine can be
described by a regular expression. Since by Theorem
4.2.1
the language recognition power of
DFSMs and NFSMs are the same, the desired conclusion follows.
4.4.1 Recognition of Regular Expressions by FSMs
THEOREM
4.4.1
Given a regular expression
r
over the set
Σ
, there is a nondeterministic finite-state
machine that accepts the language denoted by
r
.
Proof
We show by induction on the size of a regular expression
r
(the number of its opera-
tors) that there is an NFSM that accepts the language described by
r
.
BASIS:
If no operators are used, the regular expression is either
,
∅
,or
a
for some
a
∈
Σ
.
The finite-state machines shown in Fig.
4.6
recognize these three languages.
Search WWH ::
Custom Search