Context-Free Grammars (CFGs): 5 Easy Examples

Here we go over five examples of making a context-free grammar for a given set of languages. Generally we recommend to look at the properties of the language to build the CFG: how it is built up (via unions, concatenations, etc.), how counts of variables are used, edge cases, etc. The purpose of these five examples are to give an easy baseline of what is generally expected for making CFGs, and I give guidelines for them.

Timeline:
0:00 - Intro
0:15 - Example 1: (0 U 1)*
2:16 - Example 2: {0^n 1^m : n, m at least 0}
6:07 - Example 3: Palindromes
9:09 - Example 4: Union, Concatenation, Star of two CFLs
13:19 - Example 5: {a^i b^j c^k : i != j}

Easy Theory Website: https://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.