Here we show how to convert any context-free grammar (CFG) to an equivalent pushdown automaton (PDA); this video is a more up-to-date and higher-quality version of a video already on the channel.
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. In this case, we worked with a CFG for the language of strings that are not palindromes (over the alphabet {a, b}), although the particular language/CFG does not matter.
Chapters:
0:00 - Intro
0:26 - Showing CFG is correct
1:32 - Overview of CFG to PDA conversion
6:52 - Start of CFG to PDA conversion
8:04 - Dealing with start variable
8:35 - The q_loop state
10:25 - Handling terminals at top of stack
12:58 - Handling variables at top of stack
20:35 - Verifying correctness of conversion
23:54 - Outro
----------------------------------------------------------------------------------------------------------------
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.
----------------------------------------------------------------------------------------------------------------
Easy Theory Website: www.easytheory.org
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
Негізгі бет Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)
Пікірлер: 28