Theory Of Computation.
Definition: Two states ? and ? in a DFSM M, with n states, are distin- guishable if and only if there is some string w so that starting from state o when M processes w, it runs (wlog) to an accept state, but starting from ?, when M processes w, it runs an reject state. We also say that w distinguishe.s a and B In order to demonstrat that a and are distinguishable, we only have to exhibit one string w that distinguishes them. But if they are indistinguish- able, it would seem that there is no way to constructively demonstrate it since we would then have to show what M does on an infinite number of strings. But, the following shows that there is a finite way. w* of length at most n2 that distinguishes ? and ? that by examining only the strings of length n2. Claim: If a and B are distinguishable by a string w, then there is a string Corollary: If states a and B are indistinguishable, then we can determine In class, I said the length was n rather than n2, but a student noticed a flaw in the "proof" I mumbled. Fixing that flaw leads to a proof where the length is n2, rather than n. But, for the purposes of showing a finite bound on the length of the strings that we need to use, to test if ? and ? are distinguishable or not, length n2 also works. And, in the next homework you will flesh out a proof that length n really is enough. Proof of the Claim: Consider the path of states that are encountered when M processes w, starting from state a. We call that path A, and use ?'A1, ?2, , , ?k, (where k is the length of w) to denote the states in order along path A. Similarly, let B denote the path of states encountered whern M processes w, starting from state B. We denote the states along B as Now suppose that there are two positions i and j such that state a is the same as state y; and state ?? Is the same as state i. That is, the same B. The situation pair of states repeats at positions i and j in paths A and is depicted as: Definition: Two states ? and ? in a DFSM M, with n states, are distin- guishable if and only if there is some string w so that starting from state o when M processes w, it runs (wlog) to an accept state, but starting from ?, when M processes w, it runs an reject state. We also say that w distinguishe.s a and B In order to demonstrat that a and are distinguishable, we only have to exhibit one string w that distinguishes them. But if they are indistinguish- able, it would seem that there is no way to constructively demonstrate it since we would then have to show what M does on an infinite number of strings. But, the following shows that there is a finite way. w* of length at most n2 that distinguishes ? and ? that by examining only the strings of length n2. Claim: If a and B are distinguishable by a string w, then there is a string Corollary: If states a and B are indistinguishable, then we can determine In class, I said the length was n rather than n2, but a student noticed a flaw in the "proof" I mumbled. Fixing that flaw leads to a proof where the length is n2, rather than n. But, for the purposes of showing a finite bound on the length of the strings that we need to use, to test if ? and ? are distinguishable or not, length n2 also works. And, in the next homework you will flesh out a proof that length n really is enough. Proof of the Claim: Consider the path of states that are encountered when M processes w, starting from state a. We call that path A, and use ?'A1, ?2, , , ?k, (where k is the length of w) to denote the states in order along path A. Similarly, let B denote the path of states encountered whern M processes w, starting from state B. We denote the states along B as Now suppose that there are two positions i and j such that state a is the same as state y; and state ?? Is the same as state i. That is, the same B. The situation pair of states repeats at positions i and j in paths A and is depicted as
