Context-Free Grammars (CFGs): 15 Examples

Here we go through 15 examples for creating context-free grammars, and how to approach these problems generally.

Timeline:
0:00 - Intro
0:16 - Problem 1: a^n b^n
2:17 - Problem 2: a^n b^m, n more than m
4:54 - Problem 3: a^n b^m a^n
6:44 - Problem 4: a^i b^j c^k, i + j = k
9:12 - Problem 5: a^i b^j c^k, i + k = j
11:14 - Problem 6: Complement of a^n b^n
16:22 - Problem 7: Complement of a^n b^n c^n
21:51 - Problem 8: a^n b^n c^m d^m
23:17 - Problem 9: a^n b^m c^p, n at least m or m = p
26:51 - Problem 10: a^i b^j c^k, i=j or j=k
29:28 - Problem 11: a^n b^m c^m d^n
31:00 - Problem 12: Equal number of a's and b's
35:37 - Problem 13: More a's than b's
38:48 - Problem 14: Regex to CFG
41:32 - Problem 15: Balanced Parentheses

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

[riki]

Wake up babe, new Easy Theory video just dropped!

[AcidCH]

What a gem of a video

difference between you and my lecturers is you're clearly passionate about this and understand it deeply and intuitively, makes it so much easier to understand

[Owfler]

Where has this beautiful man been all my life ?

[THEGATEHUB]

I am a big fan of your content.. I think you are the best professor for the theory of computation..

[almaspernshev]

I'm senior and I work as TA for ToC because of this guy!

[AndrewPham-kz]

You are actually saving me in my upper div classes. You're the goat

[navs]

Thank you for carrying me through my ToC class

[kdxq]

I've been binge watching your videos as I am currently taking TOC as a module for my second year. Thank you so much!

[fkingraw]

Tomorrows my exam in theoretical computer science. Video came out at the right time!

[ghostprimer]

Yo, thanks for the videos! I just finished watching the CFG and CFL ones you made 4 years ago

[pedrookazaki]

Hello @Easy Theory!

Just wanted to know if you are still doing lives and pretends to post videos more regularly. Thank you very much for this channel, it is what drives me learning as a student!

[donkey_killer]

I can never get used to the intro 😂, so dramatic.

[devendrajanyani]

wasn't able to solve any on my own, am I cooked?

[JohnSmith-gpik]

How this video is great?
It's supposed to be about CFG.
CFG is a grammas free of context.
1. What is context?
2. How the Context Free Grammar is different from Context Not Free Grammar?