a. Let L be a language over an alphabet S and x and y strings in S*. x and y are

Question

a. Let L be a language over an alphabet S and x and y strings in S*. x and y are 'distinguishable' by L if there exists a string z in S* such that xz is in L, but yz is not in L. Here, xz means the concatenation of x and z. As an example, let L be the language of strings over {0, 1} in which there is an even number of both 1's and 0's. The strings x = 01 and y = 001 are distinguishable by L if we let z = 1 since xz = 011 is not in L but yz = 0011 is in L. By contrast, two strings x and y are 'indistinguishable' by L over an alphabet S if for every string z in S*, xz is in L iff yz is in L. If x is indistinguishable from y by a language L, we write this relation as 'x RL y.' Show that RL is an equivalence relation.

b. Since RL is an equivalence relation, it partitions S* (the set of all possible strings over the alphabet S) into equivalence classes. Show that a language L is regular (encoded by a DFA) if and only if the number of equivalence classes created by RL is finite.

Explanation / Answer

Given that x RL y , if for string x, y and z in S*, xz is in L iff yz is in L(i.e., both should be in L).

To show that

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.