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

(This video is outdated; see a higher quality version here:    • Context Free Grammar to Pushdown Automaton...  ) Easy Theory Website: https://www.easytheory.org GoFundMe: https://www.gofundme.com/f/easy-theor... Patreon:   / easytheoryyt   Fourthwall: https://easy-theory-llc-shop.fourthwa... 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    • What is a Context-Free Grammar?   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 Automaton (PDA)?   for more details. ---------------------------------------------------------------------------------------------------------------- If you like this content, please consider subscribing to my channel:    / @easytheory