What is the Myhill-Nerode Equivalence Relation?
ฝัง
- เผยแพร่เมื่อ 17 ก.ย. 2020
- Here we look at the Myhill-Nerode Equivalence Relation, which is another way of proving a language is not regular. Some languages cannot be shown to be regular using the pumping lemma, so we look at a "stronger" property, which is that if two different strings land in the same state, then anything read after either of them will also result in the same state. We use this on its head by considering any two different strings xz and yz that land in different states, then it must be that x and y themselves went to different states. If there are infinitely many such cases, this implies that the language cannot be regular.
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
An in-depth theory, just what i was searching for! Thanks a lot.
This cleared up a lot. Thanks!
Wonderfully explained!
0:45 why can't the pumping lemma prove L is not regular?
Assume L is regular, so it satisfies the pumping lemma for some p.
Take w = a^(p+1) b^p. This is in the language since p+1 > p.
We can write w = xyz, and we are guaranteed that |xy| = 1 so y is some non-zero amount of a's.
So x y^0 z = xz = a^(p+1-|y|) b^p, and this is not in the language since p+1-|y|
Thanks for the video!
Interesting approach, thanks for the video!
You're welcome!
thank you , I want to learn more from you :)
Thank you sir.
Thank you 💓
How did you know to choose 0* as the set of z's? How do you know that using anything from 0* as a suffix will cause xz and yz to not go to the same state, when we don't know what the DFA looks like?
In this particular case, it's because any number of 1's at the end of the string requires that exact amount of 0's at the beginning of the string to lead to an accepting state, otherwise it would be a non-accepting state (hence they are different states).
In general, perhaps it can help to try and construct and a DFA for that language. Say you wanted to first create it so that it would accept "01", since that string is part of the language. So you make a state (q0) for the 0 and then another one (q1) from that for the 1. But what about "0011"? From your first state q0, you can create another state q2, in case the first 0 is followed by another 0. To lead that to an accepting state, it would have to be followed by two other states that take the subsequent 1's.
From here on it's easy to see that extending the DFA to accept longer strings, e.g. 000111 and so on would require you to make new "branches" on the DFA for all possible lengths of 0's and 1's. You'll realize that because there are infinitely many possibilities (= infinitely many 1's at the end of the string) you'd need an infinite amount of preceding branches to reach all them.
If the language were regular, for example {0*1*} you might have an arbitrary amount of 1's at the end of your string, but those wouldn't distinguish whether the string is part of the language or not, because for any two amounts of 0's, the string would still be accepted.
Great video, thanks
You're welcome!
please answer me , how can we know if the language regular or not just by looking? I can not understand this
Why cannot use PL: I would say that for k = 1 there is only one string with the length k belonging to the language and it is "a". You can basically omit it or pump up and the result will still belong to the language.
Can you please provide a proof by pumping and by Myhill Nerode Thereom of the first language in the video? The one that is L = a* ...
4:00 Wait... If I have a language that says, I must end with a 1 at the end of a sequence (imagine a number in base 2) and I have x=0, y=1 and z=1... It will not work because xz and yz will go to the same state but not x and y. Tell me if I'm wrong but the implication does not go in the other way I think.
according to your logic, in my opinion, your hypothesis is correct but I would say your x is too small because it's not an acceptable word by itself. The language definition was "every sequence must end with a 1", but the sequence '0' by itself does not end with 1. If you would've had x="01" it would work
exactly what I'm thinking, this does not add up
good vid
The statement in red is wrong I think.
bc you can easily have zx and yz going to the same direction without y and x being the same.
From start x leads to q1 and y leads to q2. From q1 z leads to q3 and from q2 z leads to q3.
Saying the red statement follows from the green statement is the converse logical fallacy:
p -> q
_____
q -> p
Where p = “x&y going to the same state” and q = “xz&yz go to the same state”
That being said the blue statement is correct, because he negates p and q, forming the contrapositive of the green statement which is true
the red statement is false. Bc i can easily have y and x not being the same but then from the different state that they end up in have a z leading to the same case.
so xz and yz can be the same even under the assumption that x and y are not the same.
u said what i want to say
if xz and yz go to same state then its not true that x and y must go to same state
Stuck at 5:27
ive never gotten this many ads in one TH-cam video before. ever.