Myhill-Nerode theorem and minimization to eliminate useless states. The Myhill-Nerode Theorem says the following three statements are equivalent:1) The set L Í å* is accepted by some FA. (We know this means L is a regular language.)
2) L is the union of some of the equivalence classes of a right invariant (with respect to concatenation) equivalence relation of finite index.3) Let equivalence relation RL be defined by: xRLy if and only if for all z in å*, xz is in L exactly when yz is in L.
Then RL is of finite index. The notation RL means an equivalence relation R over the language L. The notation RM means an equivalence relation R over a machine M. We know for every regular language L there is a machine M that exactly accepts the strings in L. Think of an equivalence relation as being true or false for a specific pair of strings x and y. Thus xRy is true for some set of pairs x and y. We will use a relation R such that xRy <=> yRx x has a relation to y if and only if y has the same relation to x. This is known as symmetric. xRy and yRz implies xRz. This is known as transitive. xRx is true. This is known as reflexive. Our RL is defined xRLy <=> for all z in å* (xz in L <=> yz in L)
Our RM is defined xRMy <=> xzRMyz for all z in å*.
In other words d(q0, xz) = d(d(q0, x), z) = d(d(q0, y), z) = d(q0, yz) for x, y and z strings in å*.
RM divides the set å* into equivalence classes, one class for each state reachable in M from the starting state q0.
To get RL from this we have to consider only the Final reachable states of M. From this theorem comes the provable statement that there is a smallest, fewest number of states, FA for every regular language. Previous Section HOME Next Section