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 Easy Theory Website: https://www.easytheory.org If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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.