Smallest Number of Strings to Distinguish n Pairwise L -distinguishable Strings. This is an exercise from Introduction to Languages and the Theory of Computation, by John Martin. Suppose L is a language over ?, and x 1, x 2,…
x n are strings that are pairwise L -distinguishable.
3. A set of pairwise distinguishable strings: A set of strings is pairwise distinguishable with re-spect to a language L if every pair of string s in the set is distinguishable with respect to L. Example: L=(1+0)0 A set of pairwise distinguishable strings with respect.
The strings in a set S ? ?? are pairwise L-distinguishable, if for every pair x , y of distinct strings in S , x and y are L -distinguishable. De?nition independent of FAs, Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings [closed], pairwise L-distinguishable. a. L= {aiba2i | i? 0} b. L= {aibjak | k>i+ j} d. L= {aibj | j is a multiple of i } e. L= {x? {a,b}? | na(x) ww | w? {a ,b} ?} 5, L-Distinguishable Strings •We use this fact to prove a lower bound on the number of states in a DFA for L. Suppose we can ?nd a set S of k strings that are pairwise L-distinguishable. Then it is impossible for a DFA with fewer than k states to have L as its language. •If S.
• If there are infinitely many pairwise L-distinguishable strings , L is not regular. 3 The Negation: L-Equivalence • If two strings x and y are not L-distinguishable, we say that they are L-equivalent .
And it can’t take two L-distinguishable strings to the same state. •In our example, the strings 1001, 1000, and 11 are pairwise L-distinguishable for our language (0+10)*(1+?). That means that no DFA with fewer than three states could possibly have L as its language. The three-state DFA we have is thus a minimal DFA for L.
A string z having this property is said to distinguish x and y with respect to L. Equivalently, x and y are L ?distinguishable if L / x ? L / y, where L / x = {z * | xz L} 11 Distinguishing One String from Another (cont’d.) Theorem: Suppose M = (Q, , q 0, A, ) is an FA accepting L * If x and y are two strings in * that are L ?distinguishable, then *(q 0, x) ? *(q 0, y) For every n ? 2, if there is a set of n pairwise L ? distinguishable .
Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings
