next up previous
Next: A Minimization Procedure Up: Myhill - Nerode Theorem Previous: If there are

tex2html_wrap_inline342 If L is regular then tex2html_wrap_inline346 has finite index.

tex2html_wrap_inline484 If tex2html_wrap_inline346 has infinite index (numbers of equivalence classes), then L is not regular.

Proof. If x and y are distinguishable, they must take an FA for L to two different states. Therefore, infinite number of equivalence classes implies infinite number of states. tex2html_wrap_inline470



Sushil Prasad
Mon Feb 28 15:37:03 EST 2000