Context-Free Grammar to Pushdown Automaton Conversion (CFG to PDA)

Here we show how to convert any CFG (context-free grammar) into a PDA (pushdown automaton). 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.

----------------------------------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------------------------------

▶ADDITIONAL QUESTIONS◀
1. What would the PDA look like if the CFG were in Chomsky Normal Form?
2. What if the grammar were a regular grammar?

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.

[goobles]

You are the best Automata Theory youtube channel. It's a niche title, but you earned it.

[prakhartiiwarii]

Finally, a short and to-the-point video clearing out the concepts! Thanks ✌🏻

[sebastianllano]

Youre a fantatic teacher. My professor cant teach this in a 2 hour lecture and yet you did it so clearly in 9 minutes and 14 seconds. Why do I go to class?

[inarazahin]

This is the best explanation so far. It is concise and to the point. Thanks for this video. <3

[alvihabib]

You are THE MAN. Thanks for this awesome explanation!

[TheWiimaster]

FINALLY an English Video thank you so much man this was great

[thatguy]

I have an assignment due in an hour and you may have just saved me a letter grade. Thank you!

[zeitgeist]

So what if instead of B -> epsilon as a production in our CFG, we had B -> a (or B-> b). Could we still use a self loop back to qloop. In other words can we use a self loop to qloop, anytime the RHS of the production has only one symbol?

Excellent video btw!

[techademy]

The man, the myth, and the legend of theory of computation and teaching in general!

[wengeance]

So how do you represent S -> A, would this just be a self loop on qloop being (epsilon, S -> A)?

[konstantinsazhnev]

Great example and works for every CFG. The only thing I would add is if you have recursion in the same production like S --> abSb | epsilon then we have to make another loop to remove S from the stack within the loop state mentioned in the video.

[ananayarora]

Thank you thank you thank you so so so much!!!! I subscribed

[DiwashHCR]

Shouldn't the transition from the second state to q-loop be (epsilon, $ -> S) .. since the input read is nothing, stack top is a dollar and to push is S?

[dilaragoral]

Thank you so much, you saved a lot of lives!!

[albanyrebelion]

what is the significance of the read only self loop?

[沼氨]

i luv the clear way u describe. THX for saving my final💪

[Leonidesu]

Hi there, could you remove the pop-ups at the end of the video that goes to another video because it blocks your writing and we could not see anything.

[Patrick-S]

Fantastic video! This helped me so much!!!

[amanxo]

thank you man this is literally what i needed

[rosenv.]

How would this look if we accept by final state rather than empty stack?