Here we do a livestream covering everything to do with context-free languages. We cover context-free grammars (CFGs and two examples), pushdown automata (PDAs), the conversion from a CFG to a PDA, the conversion from a PDA to a CFG, the pumping lemma for context-free languages, and closure properties (as well as operations CFLs are not closed under).
Timestamps:
0:00 - Start of livestream
21:19 - Start of topics
24:10 - Definition of CFG
31:20 - Example 1 of CFG (with definitions)
41:30 - Example 2 of CFG (balanced parentheses)
47:30 - CFLs closed under union, concat, star
59:40 - Chomsky Normal Form definition
1:09:11 - CFG to CNF start
1:13:38 - Step 1 of CNF conversion
1:15:22 - Step 2 of CNF conversion
1:20:05 - Step 3 of CNF conversion
1:23:53 - Step 4 of CNF conversion
1:28:12 - Step 5 of CNF conversion
1:39:50 - PDA definition
1:45:00 - PDA example
1:49:50 - CFG to PDA
2:01:10 - PDA to CFG
2:36:30 - Proof of Pumping Lemma for CFLs
2:55:40 - Pumping Lemma for CFLs statement
2:58:50 - Proving {0^n 1^n 2^n} is not a CFL
3:07:40 - CFLs not closed under complement or intersection
3:23:10 - Wrapup
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory #gate #theory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
â–¶SEND ME THEORY QUESTIONSâ—€
ryan.e.dougherty@icloud.com
â–¶ABOUT MEâ—€
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.