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

(This video is outdated; see a higher quality version here: • Context Free Grammar t... )
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.
----------------------------------------------------------------------------------------------------------------
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.
----------------------------------------------------------------------------------------------------------------
If you like this content, please consider subscribing to my channel: / @easytheory
▶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.

[@goobles3991]

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

[@EasyTheory]

I'll accept my award and parade soon :) (thanks very much!)

[@moeyali123]

I agree

[@prakhartiiwarii]

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

[@EasyTheory]

You're welcome!

[@Shan-gn7mg]

@@EasyTheory yes please do more vids like this, it's more efficient and easy to understand.

[@Shan-gn7mg]

@@EasyTheory is that possible to do a same version for pda to cfg?

[@inarazahin5786]

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

[@EasyTheory]

You're very welcome!

[@ashleyarmenta2289]

This is the best PDA explanation video that I've found, thank you!

[@techademy9354]

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

[@thatguy7802]

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

[@matthewsocoollike]

wow. thank you so much. I was watching other videos so confused by all the math. your video made it super simple, thank you.

[@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.

[@jaeger_404]

Thank you!!! This made so much more sense than the other explanations i found

[@alvihabib]

You are THE MAN. Thanks for this awesome explanation!

[@EasyTheory]

Alvi Habib thanks very much! Make sure to check out the lecture series I'm currently doing.

[@pk-le5bb]

clear, concise, and comprehensive.
you are a godsend, thank you

[@cadencetennant3303]

Super helpful! I understand it so much better now.

[@user-cg5jo2uy3f]

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

[@melissamarlen1022]

This was such a great video! Thank you so much!

[@farwahbatool6247]

You're the man I take refuge in 😢🙌🏻💖

[@TheWiimaster456]

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

[@EasyTheory]

Lol thanks!

[@Jessislegend]

Good explanation! Much appreciated

[@woodfur00]

Perfectly explained, bless you 🙏

[@Patrick-S3]

Fantastic video! This helped me so much!!!

[@dilaragoral2259]

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

[@EasyTheory]

You're very welcome!

[@justinkuang9423]

Another great vid 👌🏻

[@ShaidaMuhammad]

Man, It was 6th video in my UA-cam search "cfg to pda" which I understood.
Thanks man.

[@EasyTheory]

5 more spots to rise up! ;)

[@ShaidaMuhammad]

@@EasyTheory Yeah, The volume was a bit slow, but headphones worked fine for me.

[@evaeunicemoreno6349]

Thanks for this! Finally, i got it ✨

[@EasyTheory]

Great!

[@FernandaRodriguez-xf3lr]

Thank you!! This is a great video

[@globalxoxo]

Amazing video Sir Alan

[@alexoxley5058]

Thank you so much, really helped!

[@sonjamariemusic]

sir. you've saved my life

[@amanxo1]

LMFAOOOOOOOOOOOOO thank you man this is literally what i needed

[@cihadozcan1035]

Thanks for neat explanation

[@cobyjonah7675]

omg you are literally the best

[@rotisosis8285]

Thank you so much now is easy to do my homework.

[@csperi-peri2447]

Great Video !

[@rosenv.1953]

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

[@jeffchong3450]

Thank you!!

[@Dakun]

you saved me, way better explanation than my professor

[@EasyTheory]

You're welcome!

[@amynguyen3131]

Thank you so much!

[@LPNorway]

Thank you so much man

[@ananayarora]

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

[@EasyTheory]

You're very welcome!

[@zeruihai6051]

Thank you sooooo sooooo much!!!!

[@fernandogmail1]

thank you 😭😭😭😭

[@wengeance8962]

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

[@EasyTheory]

Yes, correct! Or you can have two transitions that "go out of qloop and come back" but that's not necessary.

[@LasradoRohan]

Loved It

[@zeitgeist18]

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!

[@moatef1886]

To answer your question a year later, yes you should be able to simply use a self loop back to qloop when the RHS of the production has one symbol.

[@dan-cj1rr]

Thanks for the video, i have a question, i don't understand when you're in qloop why isn't it S, S ; c instead of epsilon, S ; c would make more sens for me if it was S,S ; c no ? Or does both work. Thanks

[@EasyTheory]

Because S, S -> c means "read an S" but that is already a problem because the input is over the input alphabet Sigma, not the stack alphabet Gamma.

[@shyamkannan8594]

What if the language has no terminals? Then what would go in qloop

[@pauldumitriu9237]

Hi there, I was wondering if you have any videos where we can go backwards? Going from a PDA to a cfg

[@EasyTheory]

Video coming out soon :) the CFL livestream happening in a few weeks will certainly cover this too

[@KhangNguyen-wj5jd]

What is the software you use for drawing? It is beautiful.

[@unpluggability]

i love you.

[@samjudelson]

Thanks!

[@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.

[@nabeelbaghoor1061]

Thanks a lot!!!!

[@EasyTheory]

You're welcome :)

[@albanyrebelion]

what is the significance of the read only self loop?

[@albanyrebelion]

is that the case even if a terminal isnt in the S(start) rule?

[@DiwashHCR2]

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?

[@EasyTheory]

Why would you pop $ there? The whole purpose of putting the $ on the stack at the very start is to ensure we can't go to the final state unless the stack is "empty" (other than $).

[@DiwashHCR2]

@@EasyTheory Thanks ... I thought the tuple was (input symbol, stack top symbol, push/pop)

[@EasyTheory]

@@DiwashHCR2 This is where divergence in notation comes into play -- my notation (based on the Sipser book) is: (input_symbol, thing_to_pop (or not), thing_to_push (or not)). So the first transition here pushes a $, and then pushes an S (the start variable). So when we first enter q_loop, the stack contents are $S (top of stack on the right).

[@EasyTheory]

There are some books that do force something to be popped on each transition; some others (maybe yours) does a "peek" at the top but doesn't pop; others can (maybe yours also) forces a push-only or pop-only transition.

[@tekunalogy]

❤️

[@fatimaalamour5256]

In Germany we say Ehrenmann

[@shaysarn2235]

8:48

[@armanyama3186]

Why we can't take all these in single loop on qloop state ?

[@darklord998]

I used this tutorial for a quiz and my professor marked it completely wrong :(

[@beans_potatoes]

did he say why?

[@twondai2642]

what

[@princeelliot2836]

Great video, but why not accept with empty stack and simply use two states:
(We have to assume that $ is already on the stack, though. Otherwise, this automaton would accept every input.)
The first state pushes the start-non-terminal on the stack and the second state loops over itself, while using every single rule from the CFG and pops terminals from the stack, while pushing nothing on the stack. The moment the stack is empty again, simply go back to the first state and push nothing on the stack. Our automaton should accept now, because the stack is empty.

[@princeelliot2836]

Or, if we want to have an accepting state, we could add a third state and if we have an empty stack (even without $), then we go from the second state to the third one and accept.