Context-Free Languages in 3.5 Hours (CFG, PDA, Conversions, Closure, Pumping Lemma)

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

#easytheory #gate #theory

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:

Merch:

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀

▶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.

[EasyTheory]

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

[clefang]

This pumping lemma explanation is the first time it made any sense to me after taking my school's intro to theory course this whole semester. Thank you for making these videos

[liamfennell]

This was incredibly helpful, you explained everything so well. Thank you so much.

[amishdutta]

3 hrs until my exam. I am not sleeping today. Video is looking great till now . Before seeing your video i was praying for getting passed, and 1 hr into your video i am thinking may be i can get 90 percent ;)

[pere_gin]

I usually have adblock on, but I turned it off completely for your channel, maybe you can tell other people to consider doing the same to contribute a bit more for free! I hope you grow bigger and help many more future computer scientists!!

[Unelith]

I have 1 hour 21 minutes until the exam, 2x speed for the win

[nicklasthygesen]

Does it not matter if you switch the order of step 4 and step 5 of the CNF conversion?

[shawblake]

2:00:20 How can you pop something "epsilon, 1 or 0" when they are not in the stack. Or am I wrong and every time what something is read it is popped ?