Two strings x and y are indistinguishable if:
A)?*(s, x) = ?* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
B)if for every string z ? ?* either both xz and yz are in language A on ?* or both xz and yz are not in A
C)Both above statements are true
D)None of the above

Question

Quizplus · Accepted Answer

Both statements A and B correctly define conditions under which two strings x and y are considered indistinguishable. Statement A describes indistinguishability in terms of reaching the same state in a DFA for both strings, while statement B describes it in terms of both strings, when concatenated with any string z, either both being in or both being out of a language A. These are two perspectives on the concept of indistinguishability in formal language theory and automata.

Two Strings X and Y Are Indistinguishable If