It can be easily seen that this equivalence relation R M is right invariant, i.e., if (If a state is not reachable from q 0, it can be removed without affecting the language accepted). The number of equivalence classes is therefore equivalent to the number of states of M, assuming every state is reachable from q 0. The set of strings which take the machine from q 0 to a particular state q i are in one equivalence class. So R M divides Σ* into equivalence classes. R M is an equivalence relation, as seen below. Define a relation R M on Σ* such that xR My if δ( q 0, x) = δ(q 0, y). Let L be accepted by a FSA M = ( K, Σ, δ, q 0, F). Let equivalence relation R L be defined over Σ* as follows: xR L y if and only if, for all z ∊ Σ*, xz is in L exactly when yz is in L. L is the union of some of the equivalence classes of a right invariant equivalence relation of finite index on Σ*.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |