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.
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.
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.
Remember that the initial state is visited before any character is read, so a string of n characters will trigger a sequence of n+1 states. This makes your suggestion to add 1 more character unnecessary. If n is the total number of states in the automaton, then a string of length n will be enough to apply the pigeonhole principle since, once again, n+1 states will be visited (with repetition).
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?
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.
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....
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, TH-cam
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.
19:00 Proof by mathematical induction.
41:41 Pumping lemma.
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
I love how Sipser reinforces all levels of thoought. It makes me feel more confident.
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.
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!
4:49
CFG : 1:00:00
4 hours before topic exam
Thank you professor heart heart heart
I tried the pumping length with my girlfriend. This video helped, thanks!
LMAOO
pumping 🅿️
Just realized that my entire class is based off this professors book. Didn't know he was the author
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 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.
@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 .
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.
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.
Remember that the initial state is visited before any character is read, so a string of n characters will trigger a sequence of n+1 states. This makes your suggestion to add 1 more character unnecessary. If n is the total number of states in the automaton, then a string of length n will be enough to apply the pigeonhole principle since, once again, n+1 states will be visited (with repetition).
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?
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.
Have we proved the closure under intersection(∩)
1:01:00
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....
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.
Thanks sir!
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
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
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.
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