Let us consider M got after applying (i) and (ii) to Σ, Q and δ. We write the
modified M as
( , , , , )
Q
q F
Σ δ 0
.
Let us now define a new automaton M ′ by
M
Q
q Q F
′ =
−
( , , , ,
)
Σ δ 0
.
We can see that w T M
∈
′
( ) iff δ( , )
q w Q F
0
∈ − and w T M
∉ ( ).
There fore Σ
*
( )
− =
′
L T M and there fore reg u lar.
¨
THE O REM 3: If L 1 and L 2 are regular, so is L
L
1
2
∩ [Regular sets are closed
w.r.t. Intersection]
Proof: It is important to note that
L
L
L
L
c
c c
1
2
1
2
∩ =
∪
(
)
If L 1 and L 2 are regular, then L L
c
c
1
2
,
are regular by theorem 1.
Therefore (
)
L
L
c
c c
1
2
∪
is regular by theorem 2.
Hence L
L
1
2
∩ is reg u lar.
¨
1.10 MYHILL-NERODE THEOREM
1.10.1 Myhill-Nerode Rela tions
Isomorphism
Two DFAs given by M
Q
s F
M
m m
m
= (
, , , , )
Σ δ
and N
Q
s F
N
n n
n
= ( , , , , )
Σ δ
are
said to be “isomorphic” if there is a one-to-one and onto mapping
f Q
Q
M
N
:
→
such that
(i) f s
s
M
N
( )
,
=
(ii) f
p a
f p a
M
N
(
( , ))
( ( ), )
δ
δ
=
for all P Q a
M
∈
∈
,
,
Σ
(iii) p F if f p F
M
N
∈
∈
( )
.
Isomorphic automata accept same set.
Myhill-Nerode Rela tions
Let R ⊆ Σ
* be a regular set, and let M
Q
s F
= ( , , , , )
Σ δ
be a DFA for R with no
inaccessible states.
The automaton M induces an equivalence relation ≡ M on Σ
* defined by
x
y
s x
s y
M
def
≡
⇔
=
$ , ) $ ( , )
δ (
δ
It is easy to show that the relation ≡ M is an equivalence relation, meaning
it is reflexive, symmetric and transitive.
DFA and NFA
97