Context-Free Grammars (CFGs): 5 Intermediate Examples

Here we do 5 more intermediate examples of context-free grammars. In general, I give some techniques to analyze the structure of the given language further, such as decomposing the language into a concatenation, or nesting pairs. I also give examples of where we have to analyze the structure of what the strings look like in the language, and break up the CFG into cases which can be handled separately.

Timeline:
0:00 - Intro
0:15 - Example 1: Nested Pairs
2:45 - Example 2: Concatenated Pairs
4:58 - Example 3: Non-palindromes over {0, 1}
8:29 - Example 4: Complement of {0^n 1^n 2^n : n at least 0}
15:26 - Example 5: {a^i b^j c^k : i is at most j + k}

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.