This lecture is a lot harder compared to previous ones. The pumping lemma of CFG is harder to comprehend than that of FA. But overall the material is fascinating: the equivalence of FA and RE; the equivalence of CLG and PDA; use pumping lemmas to check the limitation of FA and CLG. It is unbelievable that such clean relations can be shown. The first time that can appreciate the power of Turing machine and the genius of Turing.
In 28:53, p should be b^{|V|+1} instead of b^{|V|}+1 , consistent with the textbook. This is because if we choose the lowest repetition, the subtree has a height of |V|+1 , which gives us an upper bound of b^{|V|+1} for |vxy| .
Michael Sipser is brilliant I really doubt he wouldn't have been able to follow the proof of the CFL pumping lemma in lecture format when he first saw it as an undergrad
It seems to me in order to have a repeating variable, we would need more variables than the height of the tree, so |V|>h, and then the inequalities will be in the right order
18:20 The reason vxy p then vxy could be written in the form u' v'x'y' z' which would still imply the above lemma and u'z' != 0 so we could always reduce u vxy z -> u u' v'x'y' z' z, but now it'd be a larger string. We would want the smallest string to impose more constraints and setting vxy
40:12 "And so if they were closed under complement, De Morgan's Laws would say that closure under union and closure under complement would give you closure under intersection. But we don't have closure under intersection. So in fact, they're not closed under complement." Can someone give more details on this? I'm having a hard time understanding it.
We know that CFLs are closed under union. To prove this we can take two CFGs (call them G1 & G2 with start variables S1 & S2 respectively) and then add a new start variable S3 and new production rules which just go from S3 to either S1 or S2. We also know that CFLs are not closed under intersection. To prove this take the intersection of L1 = {a^ib^ic^j | i >=1 & j >=1} and L2 = {a^ib^jc^j | i >=1 & j >=1} and show that it is not context-free using the pumping lemma. Now DeMorgan's Law says (L1^c ∪ L2^c)^c = L1 ∩ L2. (^c being the complement). So if we assume that CFL's are closed under complement then we can use that along with their closure under union to get a CFL = L1 ∩ L2. We already know that CFLs aren't closed under intersection so our assumption that they're closed under complement is false.
27:45 Why do we need the height to be more than the number of variables for repetition? We can repeat variables with a CFL like: S -> A + B + C + D + E A -> A | a B -> B | b C -> C | c D -> D | d E -> E | e Parse tree: S A + B + C + D + E A B C D E a b c d e Here, Height = 4 and Number of Variables = 5, but repetition exists
reviews context-free languages and their relationship to regular languages. introduces the pumping lemma for proving languages are not context-free. emphasizes the importance of understanding the main ideas of problem sets and provides additional resources for reference. Timestamps [00:49-01:44] Context-free languages are more powerful than regular languages. [03:00-06:51] Discussion of problem sets and solving problems related to context-free languages. [07:16-12:55] The power and limitations of context-free languages. [14:26-19:17] Introducing the pumping lemma for context-free languages. [18:31-29:20] Explanation and proof of the pumping lemma and its conditions.
42:16 For some cuts of s1, it cannot be pumped I think (there is even/odd fashion there, but it's proof by contradiction, so one example should be enough). Let's say p is odd, then we cut where x="1" and (v, y) has same number of "0"s in that case it can be pumped, but what if p is even ? then x="1" and we are left with (p-1) which clearly cuts in unequal parts for v and y, so the number of zeros in one side (whichever) will be smaller than other side. As I mentioned earlier, since we are proving by contradiction, one example should be sufficient to show the contradiction. Any thoughts, why this wouldn't work ? Edit: I got it wrong at first glance, the answer to my statement above is: You need to show there is NO way to cut the string such that it can be pumped.
Any course materials we have are available on MIT OpenCourseWare at: ocw.mit.edu/18-404JF20. If it's not there, it wasn't given to us to publish. Best wishes on your studies!
@@mitocw Would you be able to ask the professor about making these problem set solutions available? I have already sent an email to him personally but got no response. It would really help individual learners to grasp more of this amazing content and show how MIT is #1 truly in open courses!
I'd argue all Turing Machines *do* come with an eraser, because all Turing Machines come with a write function and you could always just write a blank space
47:40 Turing starts
9:09 start of the lecture
thx bro
This lecture is a lot harder compared to previous ones. The pumping lemma of CFG is harder to comprehend than that of FA. But overall the material is fascinating: the equivalence of FA and RE; the equivalence of CLG and PDA; use pumping lemmas to check the limitation of FA and CLG. It is unbelievable that such clean relations can be shown.
The first time that can appreciate the power of Turing machine and the genius of Turing.
In 28:53, p should be b^{|V|+1} instead of b^{|V|}+1 , consistent with the textbook. This is because if we choose the lowest repetition, the subtree has a height of |V|+1 , which gives us an upper bound of b^{|V|+1} for |vxy| .
Great lecture, this has help me a lot to understand the book
nobody asked
@@w0nnafight yet you read it
29:07 moment of respect
Michael Sipser is brilliant I really doubt he wouldn't have been able to follow the proof of the CFL pumping lemma in lecture format when he first saw it as an undergrad
It seems to me in order to have a repeating variable, we would need more variables than the height of the tree, so |V|>h, and then the inequalities will be in the right order
18:20
The reason vxy p then vxy could be written in the form u' v'x'y' z' which would still imply the above lemma and u'z' != 0
so we could always reduce u vxy z -> u u' v'x'y' z' z, but now it'd be a larger string.
We would want the smallest string to impose more constraints and setting vxy
ThNKAS prof!!! I now understand the pumping lemma for context free languages thanks to your kindness and knowledge sharing 😎😎😎😎
40:12 "And so if they were closed under complement, De Morgan's Laws would say that closure under union and closure under complement would give you closure under intersection. But we don't have closure under intersection. So in fact, they're not closed under complement."
Can someone give more details on this? I'm having a hard time understanding it.
We know that CFLs are closed under union.
To prove this we can take two CFGs (call them G1 & G2 with start variables S1 & S2 respectively) and then add a new start variable S3 and new production rules which just go from S3 to either S1 or S2.
We also know that CFLs are not closed under intersection.
To prove this take the intersection of L1 = {a^ib^ic^j | i >=1 & j >=1} and L2 = {a^ib^jc^j | i >=1 & j >=1} and show that it is not context-free using the pumping lemma.
Now DeMorgan's Law says (L1^c ∪ L2^c)^c = L1 ∩ L2. (^c being the complement).
So if we assume that CFL's are closed under complement then we can use that along with their closure under union to get a CFL = L1 ∩ L2. We already know that CFLs aren't closed under intersection so our assumption that they're closed under complement is false.
27:45
Why do we need the height to be more than the number of variables for repetition?
We can repeat variables with a CFL like:
S -> A + B + C + D + E
A -> A | a
B -> B | b
C -> C | c
D -> D | d
E -> E | e
Parse tree:
S
A + B + C + D + E
A B C D E
a b c d e
Here, Height = 4 and Number of Variables = 5, but repetition exists
it needs to be a minimal parse tree as well, in this case you couldn't take any of the A,B,C,D,E rules as they're extraneous
reviews context-free languages and their relationship to regular languages.
introduces the pumping lemma for proving languages are not context-free.
emphasizes the importance of understanding the main ideas of problem sets and provides additional resources for reference.
Timestamps
[00:49-01:44] Context-free languages are more powerful than regular languages.
[03:00-06:51] Discussion of problem sets and solving problems related to context-free languages.
[07:16-12:55] The power and limitations of context-free languages.
[14:26-19:17] Introducing the pumping lemma for context-free languages.
[18:31-29:20] Explanation and proof of the pumping lemma and its conditions.
plzz give me problem set
42:16 For some cuts of s1, it cannot be pumped I think (there is even/odd fashion there, but it's proof by contradiction, so one example should be enough). Let's say p is odd, then we cut where x="1" and (v, y) has same number of "0"s in that case it can be pumped, but what if p is even ? then x="1" and we are left with (p-1) which clearly cuts in unequal parts for v and y, so the number of zeros in one side (whichever) will be smaller than other side. As I mentioned earlier, since we are proving by contradiction, one example should be sufficient to show the contradiction. Any thoughts, why this wouldn't work ?
Edit: I got it wrong at first glance, the answer to my statement above is: You need to show there is NO way to cut the string such that it can be pumped.
Where can I get access to the 0.x problems solutions? Please
Any course materials we have are available on MIT OpenCourseWare at: ocw.mit.edu/18-404JF20. If it's not there, it wasn't given to us to publish. Best wishes on your studies!
@@mitocw Would you be able to ask the professor about making these problem set solutions available? I have already sent an email to him personally but got no response. It would really help individual learners to grasp more of this amazing content and show how MIT is #1 truly in open courses!
where the hell is deterministic pda's
12:38 is it because regular language also CFL?
Of course the class of regular languages is a subset of the class of context free languages
Great lecture!
Thank you for sharing!
This is a great course!
0:00 saved my grade
I'd argue all Turing Machines *do* come with an eraser, because all Turing Machines come with a write function and you could always just write a blank space
24:59 There's hope for me...
Good old days at cs university...
why arent your days good now?
W vid no cap
40:00 interesting
30:00