Information Technology Reference
In-Depth Information
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿
￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
L ( M 2 )
￿￿￿
￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
L 1
L 2
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿
￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿
￿￿￿
L ( M 1 )
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿
￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
￿￿￿￿￿￿￿￿
Figure 4.1 9 (a) Th e intersection L 1
L 2 of two sets L 1 and L 2 canbeobtainedbytakingthe
compleme nt L 1 ∪ L 2 of the union L 1 ∪ L 2 of their complements. (b) If L ( M 1 ) ⊆ L ( M 2 ) ,then
L ( M 1 ) ∩ L ( M 2 )=
.
that can recognize the concatenation, union and Kleene closure of regular languages. We now
show that algorithms exist for a number of decision problems concerning finite-state machines.
THEOREM 4.6.2 There are algorithms for each of the following decision problems:
a)
For a finite-state machine M and a string w , determine if w
L ( M ) .
b)
For a finite-state machine M , determine if L ( M )=
.
For a finite-state machine M , determine if L ( M )=Σ .
c)
L ( M 2 ) .
e) For finite-state machines M 1 and M 2 , determine if L ( M 1 )= L ( M 2 ) .
Proof To a n s w e r ( a ) it suffices to supply w to a deterministic finite-state machine equiva-
lent to M and observe the final state after it has processed all letters in w .Thenumberof
stepsexecutedbythismachineisthelengthof w .Question ( b ) is answered in Lemma 4.5.2 .
We need only determine if the language contains strings of length less than m ,where m is
the number of states of M . This can be done by trying all inputs of length less than m .
The answer to question ( c ) is the same as the answer to “Is L ( M )=
For finite-state machines M 1 and M 2 , determine if L ( M 1 )
d)
?” The answer to
question ( d ) is the same as the answer to “Is L ( M 1 )
L ( M 2 )=
?” (See Fig. 4.19 (b).)
Since FSMs that recognize the complement and intersection of regular languages can be
constructed in a finite number of steps (see the proof of Theorem 4.6.1 ), we can use the
procedure for ( b ) to answer the question. Finally, the answer to question ( e ) is “yes” if and
only if L ( M 1 )
L ( M 2 ) and L ( M 2 )
L ( M 1 ) .
4.7 State Minimization*
Given a finite-state machine M , it is often useful to have a potentially different DFSM M min
with the smallest number of states (a minimal-state machine) that recognizes the same language
L ( M ) . In this section we develop a procedure to find such a machine recognizing a regular
language L . As a step in this direction, we define a natural equivalence relation R L for each lan-
guage L and show that L is regular if and only if R L has a finite number of equivalence classes.
4.7.1 Equivalence Relations on Languages and States
The relation R L is used to define a machine M L .When L is regular, we show that M L is a
minimal-state DFSM. We also give an explicit procedure to construct a minimal-state DFSM
Search WWH ::




Custom Search