I finally understand the Pumping Lemma for regular languages!! 😊 I didn’t quite get it by reading the proof in the ’Sipser’ book the first time; but after this really great lecture by the author himself it’s all clear. He gave just the right amount of intuition necessary. Thank you Prof, and thank you MIT for making these courses available to everyone who wants to learn.
This series of lectures by Professor Sipser is absolutely great! This is the first time I get a clear picture of FAs. There is only one thing could be mentioned that I think will greatly improve the intuition of the pumping lemma: that any language with finite number of strings is a FA. Even though it is a trivial result, but that will imply the pumping lemma is dealing with languages with infinite number of strings. Further with the property that all FA have finite number of states, we can now understand that the pumping lemma is something related to "loop" of states.
One point I think he should have emphasized more is that concatenation with the empty language gives you the empty language. Then it becomes obvious why no arrow is the same as the arrow with and the empty language.
What is the relation between concatenation of empty language and that arrow?i think the reason why he labeled it with the empty language is that even if the computer read the empty string it cant go empty language's path. Because empty language doesn't contain empty string as a member.
I see, so GNFA is just a superset of DFA and NFA, meaning one can create a DFA or NFA using GNFA. Wouldn't it be less confusing if it was just called GFA or Generalized Finite Automata?
I think in the proof of the pumping lemma, p needs to be (at least) 1 + [the number of states in M]: only in that case is the input string guaranteed to repeat a state.
this is correct. consider the pigeonhole theorem: if we have P states and a string of length P+1, then there is necessarily a repeated state. then the route the states took between the two repeated states (call it y) can repeated how ever many times you’d like. so you have x, the string before the repetition and z, the string after, and so an accepted string is xy*z where the * means you can repeat it many times.
52:23 What if pumping's lemma holds for D? Is it necessarilly regular? Because, according to the lecture, pumping's lemma holds for all regular expressions, but it is not said that it holds ONLY for regular expressions. At least according to the lecture. So if it doesn't hold, D is not regular, but what if it holds?
Usually you construct a FA directly if the language is regular, because it is really hard to show all cases don't have the pumping property. Try his example of equal number of 01 and 10 is regular.
anyone mind explaining why, when we're trying to prove D is not regular by contradiction, we can't take 010101 as a string, where the first 01 is x, the second 01 is y and the last 01 is z. We take the y and repeat it as much as needed and we still stay in the language. why is that not possible? is it because 01 is same as 01010101....
Doubt at Checkin 3.1 at 28:30 Shouldn't the answer be B as we showed in the last lecture how to convert NFAs to DFAs, just like that we have to show GNFAs to DFAs even if we assume the transitions to be a single symbol ?
@@chilldude1337 You got it the other way around. All NFAs are also GNFAs. However you can indeed convert any GNFA to a DFA. One possible way to do this is to convert the GNFA to a regular expression, convert the regular expression to an NFA, and finally convert the NFA to a DFA.
@@wenjunliu You can convert any GNFA to a DFA. One possible way to do this is to convert the GNFA to a regular expression, convert the regular expression to an NFA, and finally convert the NFA to a DFA.
This is fascinating stuff , but I have to get this off my chest : You speak the words " and uhm" , " Uh " , " so ..", " and " etc ............. soooooo many times in a minute it utterly distracts me from the subject. You Sir , are not a good teacher .
That I disagree. The professor try to find good wordings to describe the idea, but that is just a secondary factor. Don't try to follow what he says verbally, try to follow what he intends to show.
I finally understand the Pumping Lemma for regular languages!! 😊 I didn’t quite get it by reading the proof in the ’Sipser’ book the first time; but after this really great lecture by the author himself it’s all clear. He gave just the right amount of intuition necessary. Thank you Prof, and thank you MIT for making these courses available to everyone who wants to learn.
"Some make simple things complex and Some make complex things simple"
Thank you, Sir Sipser❤️
Thank you, MIT
Thank you, RUclips
I love how Sipser reinforces all levels of thoought. It makes me feel more confident.
19:00 Proof by mathematical induction.
41:41 Pumping lemma.
This series of lectures by Professor Sipser is absolutely great! This is the first time I get a clear picture of FAs.
There is only one thing could be mentioned that I think will greatly improve the intuition of the pumping lemma: that any language with finite number of strings is a FA. Even though it is a trivial result, but that will imply the pumping lemma is dealing with languages with infinite number of strings. Further with the property that all FA have finite number of states, we can now understand that the pumping lemma is something related to "loop" of states.
It's been 8 years since I studied theory of computation in my university, you make me feel like it was yesterday! Thank you Mr. Sipser
20 years after doing CS degree, finally understand the pumping lemma.
so ur saying its gonna take me 20 years to understand my HW thats due tonight
@@texastalent3300 Finish a homework and understand are two different things. You can apply the lemma without understanding it, that is for sure.
pumping 🅿️
4 hours before topic exam
Thank you professor heart heart heart
These lectures are simply amazing. I was hopeless in my university when we started automata theory, but now it's all getting clear slowly. Thanks!
great lectures, but his pessimism about students gives me anxiety about what my professors used to think about me 😝
💯 those belittling comments would literally crush people with lack of confidence
I am student from RIT and this is excellent supplementary material for CSCI 262: intro to cs theory
RIT what is that? your backyard? LOL!
@@w0nnafight Rochester Institute of Technology. It actually has a somewhat known theoretical computer science research group.
@@w0nnafight your name says it all.
4:49
CFG : 1:00:00
One point I think he should have emphasized more is that concatenation with the empty language gives you the empty language.
Then it becomes obvious why no arrow is the same as the arrow with and the empty language.
What is the relation between concatenation of empty language and that arrow?i think the reason why he labeled it with the empty language is that even if the computer read the empty string it cant go empty language's path. Because empty language doesn't contain empty string as a member.
I tried the pumping length with my girlfriend. This video helped, thanks!
LMAOO
I see, so GNFA is just a superset of DFA and NFA, meaning one can create a DFA or NFA using GNFA. Wouldn't it be less confusing if it was just called GFA or Generalized Finite Automata?
I think in the proof of the pumping lemma, p needs to be (at least) 1 + [the number of states in M]: only in that case is the input string guaranteed to repeat a state.
this is correct. consider the pigeonhole theorem: if we have P states and a string of length P+1, then there is necessarily a repeated state. then the route the states took between the two repeated states (call it y) can repeated how ever many times you’d like. so you have x, the string before the repetition and z, the string after, and so an accepted string is xy*z where the * means you can repeat it many times.
@53:23, 1, since i >=0, when i ==0, y is an empty string, right ? 2, could x or z be an empty string ? so s = y...y, p >=1 .
Thanks sir!
52:23 What if pumping's lemma holds for D? Is it necessarilly regular?
Because, according to the lecture, pumping's lemma holds for all regular expressions, but it is not said that it holds ONLY for regular expressions. At least according to the lecture. So if it doesn't hold, D is not regular, but what if it holds?
Usually you construct a FA directly if the language is regular, because it is really hard to show all cases don't have the pumping property. Try his example of equal number of 01 and 10 is regular.
Have we proved the closure under intersection(∩)
Just realized that my entire class is based off this professors book. Didn't know he was the author
anyone mind explaining why, when we're trying to prove D is not regular by contradiction, we can't take 010101 as a string, where the first 01 is x, the second 01 is y and the last 01 is z. We take the y and repeat it as much as needed and we still stay in the language.
why is that not possible? is it because 01 is same as 01010101....
Doubt at Checkin 3.1 at 28:30 Shouldn't the answer be B as we showed in the last lecture how to convert NFAs to DFAs, just like that we have to show GNFAs to DFAs even if we assume the transitions to be a single symbol ?
We cannot convert all GFNAs to DFA as DFA is only a type of GNFA.
Assuming that, what would be the end purpose of converting GNFAs to DFAs?
All NFAs can be converted into DFAs. Because GNFAs are also NFAs, we can assume that GNFAs can be converted into DFAs.
@@chilldude1337 You got it the other way around. All NFAs are also GNFAs.
However you can indeed convert any GNFA to a DFA. One possible way to do this is to convert the GNFA to a regular expression, convert the regular expression to an NFA, and finally convert the NFA to a DFA.
@@wenjunliu You can convert any GNFA to a DFA. One possible way to do this is to convert the GNFA to a regular expression, convert the regular expression to an NFA, and finally convert the NFA to a DFA.
I don’t particularly like the way he talks about students not getting the correct answer. Stuff like that really turns me off math courses.
I don't think he meant that in a bad way though, I suppose he was just worried about the fact that his students understood what he meant.
I get that he uses induction to prove GNFA, but the really uses a proof by contradiction here with an induction flavor added to it.
1:01:00
smart is the new sexy, how you explain the knowledge is so damn sexy
are you hitting on our teacher, mademoiselle ?
im so down bad please give me a chance
This is fascinating stuff , but I have to get this off my chest :
You speak the words " and uhm" , " Uh " , " so ..", " and " etc ............. soooooo many times in a minute it utterly distracts me from the subject.
You Sir , are not a good teacher .
That I disagree. The professor try to find good wordings to describe the idea, but that is just a secondary factor. Don't try to follow what he says verbally, try to follow what he intends to show.
I'm not sure if using filler words makes him a bad teacher, albeit bad speaker.
1) this shit is not fascinating
2) he is a good teacher, albeit a bit fast