Nerode equivalence

Definition 2.3.1: For a language L _ _*, define the binary relation L-equivalence, written __L, on _* as follows: for each x,y____* x __L y if x\L = y\L. The number of equivalence classes is the index of __L.

Example: L = 0*0 _ 00 since 0\L = 0* = 00\L 0 ± 1 since 0\L = 0* but 1\L = _L has two classes, [0] = 0* and [1] = strings with ‘1’

Assertion: L-equivalence is an equivalence relationon _* for every L _ _*.

• x _ x for all x_ _*

• x _ y implies y _ x for all x,y_ _*

• w _ x and x _ y imply w _ y for all w,x,y_ _*

Previous slide

Next slide

Back to first slide

View graphic version