What is the Myhill-Nerode Equivalence Relation?
Vložit
- čas přidán 7. 09. 2024
- 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.
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|
Assume L is regular, and that exists a p that satisfies the pumping lemma.
We want to show that for a given p, any w in L, that has length of at least p follows the pumping lemma.
W = a^q b^r, where 0 = p, and q>r
We can divide the w as follows: x = a^(q-r), y= a^r b^r, and z is the empty string.
xy^(i)z is the string a^(q-r) a^(ri) b^(ri)
q-r + ri > ri, for all q>r, and i >=0
So, L follows the pumping lemma, but the pumping lemma isn’t a sufficient condition for a language to be regular, so it can’t be used to proof that L isn’t regular.
@@laersonverissimo1715 You reordered the a's and b's when expanding y^i, it isn't a^(ri) b^(ri) but rather (a^r b^r)^i
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
This cleared up a lot. Thanks!
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
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.
Wonderfully explained!
Interesting approach, thanks for the video!
You're welcome!
Thanks for the video!
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
Great video, thanks
You're welcome!
Thank you sir.
please answer me , how can we know if the language regular or not just by looking? I can not understand this
thank you , I want to learn more from you :)
Thank you 💓
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.
if xz and yz go to same state then its not true that x and y must go to same state
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* ...
good vid
ive never gotten this many ads in one CZcams video before. ever.
Stuck at 5:27