Hey, you explain complicated concepts in an easy to follow manner and make things quite intuitive. Please continue to post these types of videos, they are absolutely carrying me :)
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.
At 20:00 when he zooms out and I'm like: “yes! I finally understand it!” Then I look at the diagram and think to myself, “what is this madness, anyways..”
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
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...)
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.
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.
Hey, you explain complicated concepts in an easy to follow manner and make things quite intuitive. Please continue to post these types of videos, they are absolutely carrying me :)
This monstrosity of a PDA is the most beautiful thing I've ever seen. Thanks so much
PDA = Kamala Harris
@@KarenWasherGrudzien How dare you disrespect PDA like that
you made PDAs seem so simple here, thanks so much
Thanks for taking your time helping us. Best video's on this topic imo.
Thanks to you I’m ahead in class, you sir sure know how to teach!!
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.
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
Amazing how you managed to turn the most simple PDA's out there that GFA are into this 12 state automata abominatio.
Yo thanks so much I've been struggling to understand this and now it finally makes sense!
This is great. it's very useful. thx for the great tips and tricks in this video.
At 20:00 when he zooms out and I'm like: “yes! I finally understand it!” Then I look at the diagram and think to myself, “what is this madness, anyways..”
woah... this is super intuitive, thank you!
هذا الرجل خارق 😂🔥
you are a life saver I swear, thank you so much
Thanks for the great video! just wondering, why do you wear your apple watch upside down? Never seen someone do that before!
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.
Thank you sir.very very helpful.
Thanks for the video!
you are the best bro!!!
Thanks so much! This is the best video, explains everything so well! Please marry me I love you!
btw I was the 781st like, thought that you should know
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...)
thanks broo
3:49 why "without loss of generality"??
legend, saved my ass🙂
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.
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.
Jones Christopher Anderson Steven Young Anthony
take it to the 1.75x, ma duud explains it like he's on crack
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