very good lecture, But I initially couldn't understand the concept of reading and handling the terminal symbols so I did some research and found this out, I just wished he could have explained better instead of saying reading-off which makes, no sense, Anyway what he actually means, consider we are given a CFG and we are also given a string, and we are asked to check if we the given CFG, accepts the string or not by using PDA, (which is equivalent to the given CFG), so basically we want to see if we get to the final state when we try to compute/ process the given string by feeding it to our equivalent PDA. so now we are going to follow the said rules, we are initially going to push the Starting symbol, which generally is Non-Terminal, since it is a CFG, then we are going to follow through the rules, or we can say we are going to traverse through all possible choices/ derivations, of the grammar, when we find ourself in the state where the top of the stack is equal to our string we are going to move the pointer of our string to +1 and continue through the stack, at some point if there really exists some derivation which gives us the required string then we will definitely read through all the characters of the string and at the same time we will have no content in our stack, except the dollar symbol, and if the are in this situation, we can say that the PDA built off of the CFG accepts the given string.
if S is in the stack doesn't it mean we read S and then we pop it (at around 14:40) like in case of terminals when we encounter a in the stack we read it and pop it
The ending justification why the PDA and the CFG are equivalent was a bit handwavy. I understand the video isn't dedicated to "hard-proving" it mathematically, but a list of resources in the description would've been nice.
Why you only push one element at the stack? I read that it is possible to push multiple. Your drawings would be much simpler to undestand, and have the same meaning.
One of the issues I cant figure out is why there are no inputs (or all inputs are empty) in this PDA. If we're reading in a string to confirm its correctness, wouldn't we need some inputs to direct our PDA in the right direction?
when u say "input" i assume it's those "a" and "b" u talking abt? and u said "reading a string to confirm its correctness" i assume u want to test word like "ab" on the PDA? if so then i can tell u that it's done at "qloop" for example if u wanna test "ab" then u can follow the line and go through the loops at the bottom and then get a stack like "aPb$" and then when u pop the "a" from the "aPb$" u will read "a" cuz "a,a ->e" means "reading a, pops a and push nothing to the stack". unless he wrote e,a ->e then u only pops "a" without reading it. and then after u follow the lines and go through the stack u should result with "ab". (i can't explain in more detail without drawing out the path so...yh u gotta just imagine what im saying...)
This monstrosity of a PDA is the most beautiful thing I've ever seen. Thanks so much
PDA = Kamala Harris
you made PDAs seem so simple here, thanks so much
Thanks for taking your time helping us. Best video's on this topic imo.
Amazing how you managed to turn the most simple PDA's out there that GFA are into this 12 state automata abominatio.
very good lecture, But I initially couldn't understand the concept of reading and handling the terminal symbols so I did some research and found this out, I just wished he could have explained better instead of saying reading-off which makes, no sense, Anyway what he actually means, consider we are given a CFG and we are also given a string, and we are asked to check if we the given CFG, accepts the string or not by using PDA, (which is equivalent to the given CFG), so basically we want to see if we get to the final state when we try to compute/ process the given string by feeding it to our equivalent PDA.
so now we are going to follow the said rules, we are initially going to push the Starting symbol, which generally is Non-Terminal, since it is a CFG, then we are going to follow through the rules, or we can say we are going to traverse through all possible choices/ derivations, of the grammar, when we find ourself in the state where the top of the stack is equal to our string we are going to move the pointer of our string to +1 and continue through the stack, at some point if there really exists some derivation which gives us the required string then we will definitely read through all the characters of the string and at the same time we will have no content in our stack, except the dollar symbol, and if the are in this situation, we can say that the PDA built off of the CFG accepts the given string.
Yo thanks so much I've been struggling to understand this and now it finally makes sense!
19:04 Completing the example head to toe clears the concept ❤
Awesome explanation brotha. I'd like to add that I think the entire PDA could've been encapsulated using just two states with multiple self-loops
you are a life saver I swear, thank you so much
Thanks to you I’m ahead in class, you sir sure know how to teach!!
This is great. it's very useful. thx for the great tips and tricks in this video.
هذا الرجل خارق 😂🔥
woah... this is super intuitive, thank you!
you are the best bro!!!
Thanks for the great video! just wondering, why do you wear your apple watch upside down? Never seen someone do that before!
Thanks for the video!
Thank you sir.very very helpful.
if S is in the stack doesn't it mean we read S and then we pop it (at around 14:40) like in case of terminals when we encounter a in the stack we read it and pop it
Thank you so much.
thanks broo
3:49 why "without loss of generality"??
The ending justification why the PDA and the CFG are equivalent was a bit handwavy. I understand the video isn't dedicated to "hard-proving" it mathematically, but a list of resources in the description would've been nice.
Why you only push one element at the stack? I read that it is possible to push multiple. Your drawings would be much simpler to undestand, and have the same meaning.
One of the issues I cant figure out is why there are no inputs (or all inputs are empty) in this PDA. If we're reading in a string to confirm its correctness, wouldn't we need some inputs to direct our PDA in the right direction?
when u say "input" i assume it's those "a" and "b" u talking abt? and u said "reading a string to confirm its correctness" i assume u want to test word like "ab" on the PDA? if so then i can tell u that it's done at "qloop" for example if u wanna test "ab" then u can follow the line and go through the loops at the bottom and then get a stack like "aPb$" and then when u pop the "a" from the "aPb$" u will read "a" cuz "a,a ->e" means "reading a, pops a and push nothing to the stack". unless he wrote e,a ->e then u only pops "a" without reading it. and then after u follow the lines and go through the stack u should result with "ab". (i can't explain in more detail without drawing out the path so...yh u gotta just imagine what im saying...)
take it to the 1.75x, ma duud explains it like he's on crack
Jones Christopher Anderson Steven Young Anthony
Davis Shirley Miller Donna Anderson Kevin
There's no F'n way you would get that from reading the book. This is ridiculous, this class is being taught so horribly.
the goat