Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)
Vložit
- čas přidán 29. 07. 2024
- Here we show how to convert any context-free grammar (CFG) to an equivalent pushdown automaton (PDA); this video is a more up-to-date and higher-quality version of a video already on the channel.
The key idea is to simulate the derivation of some string in the CFG on the stack itself of the PDA. The construction involves building 4 "base" states, and then self loops on the third state for each terminal. Initially push on a $, then the start variable, and pop the $ going to the 4th state. Then, add a series of transitions for every rule, popping the LHS variable, and then pushing on the RHS in reverse order. In this case, we worked with a CFG for the language of strings that are not palindromes (over the alphabet {a, b}), although the particular language/CFG does not matter.
Chapters:
0:00 - Intro
0:26 - Showing CFG is correct
1:32 - Overview of CFG to PDA conversion
6:52 - Start of CFG to PDA conversion
8:04 - Dealing with start variable
8:35 - The q_loop state
10:25 - Handling terminals at top of stack
12:58 - Handling variables at top of stack
20:35 - Verifying correctness of conversion
23:54 - Outro
----------------------------------------------------------------------------------------------------------------
What is a context-free grammar? It is a set of 4 items: a set of "variables," a set of "terminals," a "start variable," and a set of rules. Each rule must involve a single variable on its "left side", and any combination of variables and terminals on its right side. See • Context-Free Grammars ... for more details.
What is a pushdown automaton? It is a finite state machine, where on each transition, items can be pushed or popped off of a stack it has, which has unlimited height. See • What is a Pushdown Aut... for more details.
----------------------------------------------------------------------------------------------------------------
Easy Theory Website: www.easytheory.org
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
This monstrosity of a PDA is the most beautiful thing I've ever seen. Thanks so much
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.
Yo thanks so much I've been struggling to understand this and now it finally makes sense!
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!
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 ❤
Thanks for the video!
you are the best bro!!!
Thank you sir.very very helpful.
هذا الرجل خارق 😂🔥
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
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!
thanks broo
3:49 why "without loss of generality"??
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
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
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.
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