Conversion from Context-Free Grammar to Pushdown Automaton

(This video is outdated; see a higher quality version here: https://www.youtube.com/watch?v=GwS__G2M8mU&ab_channel=EasyTheory)

Easy Theory Website: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio
Patreon: https://www.patreon.com/EasyTheoryYT
Fourthwall: https://easy-theory-llc-shop.fourthwall.com
Problem Solving channel: ​⁠ @easytheoryprobsolve

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 https://www.youtube.com/watch?v=h1OSmLSacNA&ab_channel=EasyTheory 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 https://www.youtube.com/watch?v=Br44Zxv84-Q&ab_channel=EasyTheory for more details.

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

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1