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}

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

[flamediamond]

Never thought I'd see a video on such a niche topic, thanks to his video I'm able to do my CS Theory assignments

[julien]

if i ever manage to pass my computer theory class, it'll be thanks to you !

thanks for the video man !

[senugege]

man i am litterally crying that i couldnt somehow find your channel and videos before, i had an exam last friday and luckily i passed it but... with the least amount of points to pass it, i didnt learn the lecture from any videos or so i only used the resources and lecture videos of the prof and script, as i found a video of you a couple days prior i watched it bc i had nothing to do after the exam month and the lecture seems right now pretty interesting and cool, i think its frankly unimaginable, i have always thought that this lecture is a phase i have to learn it and i will just forget it and dont ever find it interesting or important to even give a bit of time to, thank you for making me like the lecture and making me have a bit of interest, after all you are doing an amazing job with the whole lecture videos and the way you are explaining things are great!!!

[CLG]

I have a fighting chance now to pass my midterm because of these videos. Salute to you for making this series.

[HNMCK]

These videos are so helpful! Thank you for taking the time to make them.

[hansolo]

This guy is so goated, best explanations on youtube

[kin_]

very helpfull thank you very much, help in developing skills to think about CFG!

[davidtorres]

This video was the best at helping me understand basic language theory! I have a test soon and I feel confident I'll do well.

[vimalathithand]

Just wonderful, u r an awsome teacher ! Thanks a lott!!

[unexpectedfox]

Thanks for your explanation. It helps me a lot

[hanaviyano]

Thank you very much for making these videos! You have helped me so soooo much!

[colonelh.s.l.]

Nice video! For your example 2, would it be fine to say S--> 0S | 1S | E?

[benasabu]

Sir i think for 0*1*, the production rule must be S->0S | epsilon | P, P-> 1P, E. as a string of zero is possible and belongs to the language and cannot be produced by the rule you had written at 6:05

[abhijatchauhan]

In the last problem, for the scenario of having i > j, shouldn't the "a"s be first? The grammar given for that will have some "a"s after b, thereby putting them out of order. What about A_i>j -> aA_i>j | aX, then have X -> aXb | epsilon

[excorific]

For example 2, could we just do S->AC, A-> 0A | e, C-> 1C | e?

[nahomaseged]

thanks teacher, but in the last example what if we add more condition which is i!=j or j !=k ?

[jamescommon]

For the last question. I think the languages which are: either i or j is equal to 0 are cannot be written by your grammar. Am I right?

[bradleetulio]

you forgot to account for the case when a is zero or when b is zero as such the cfg can not produce a string like : bc or even ac, so your cfg can produce only in L{a^ib^jc^k i!=j, i and j >0}