A few properties satisfied by ≡ M are as follows:
(a) It is a right congruence: for any x y
,
*
∈ Σ and a ∈ Σ,
x
y xa
y
M
M
a
≡
⇒ ≡
Proof: Assume x
y
M
≡
.
Therefore we have
$ ( , )
( $ , ), )
( $ ( , ), )
δ
δ δ (
δ δ
s xa
s x a
s y a
=
=
(by assumption)
= s ya
$ ( , )
δ
¨
(b) It refines R : for any x y
,
*
∈ Σ ,
x
y
x R
y R
M
≡
⇒ ∈ ⇔ ∈
(
).
Proof: Since $ ( , ) $ ( , ),
δ
δ
s x
s y
=
which is either an accept state or a reject state,
so either both x and y are accepted or both are rejected.
¨
(c) It is of “Finite index”: i.e., it has only finitely many equivalence class.
This is because there is exactly one equivalence class
{
| $ ( , )
}
*
x
s x q
∈
=
Σ δ
corresponding to each state q of M.
Hence the equivalence relation ≡ on Σ
* is a “Myhill-Herode relation” for R if it
satisfies properties (a), (b) and (c). i.e., if it is a right congruence of finite index
refining R.
1.10.2 Myhill-Nerode The o rem
Let R ⊆ Σ
* . The following statements are equivalent.
(i) R is regular
(ii) There exists a Myhill-Nerode relation for R
(iii) The relation ≡ R is of finite index.
(The proof is beyond the scope of this book).
Ì Exam ple 1.10.1: Using Myhill-Nerode Theorem verify whether
L a b n
n n
=
≥
{
:
}
0 is regular or not.
Solu tion
This is done by determining the ≡ R -classes. If k m
≠ , then a
a
k
L
m
/
≡
, since
98
Theory of Automata, Formal Languages and Computation