(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.
Негізгі бет Context-Free Grammar to Pushdown Automaton Conversion (CFG to PDA)
Пікірлер: 86