Question
Consider a regular language L, words w1, w2 L and words w3, w4 L. Which one of the following statements is true? a) w1 and
Consider a regular language L, words w1, w2 L and words w3, w4 L. Which one of the following statements is true?
a) w1 and w3 must be distinguishable by L.
b) w1 and w2 must be distinguishable by L.
c) w1 and w2 must be indistinguishable by L.
d) w3 and w4 must be distinguishable by L.
The correct answer is (a).
But I don't understand why is it so. I know that:
Two strings x * and y * are called distinguishable relative to L if there is a string z * such that exactly one of xz and yz is in L. In other words, such that either xz is in L and yz is not in L, or yz is in L and xz is not in L.
Two strings x * and y * are called indistinguishable relative to L if there is a string z * such that either both xz and yz are in L, or neither of them is in L.
Given that the correct answer is (a) and looking at the other options given, I see that there is some relationship when both words are taken from L (w1 & w2) or both, not from L (w3 & w4) we cannot say whether they are distinguishable or indistinguishable. But when the two words are taken one from L and the other, not from L they are distinguishable.
I inferred this using the given correct answer and looking at the other options on the question but I don't understand why is this so. Can you explain this to me?
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started