Context-Free Grammars (CFG) and Context-Free Languages (CFL) - what are they?

Here we start context-free grammars (CFG) and context-free languages (CFL), which are the languages of CFGs. The idea is to have every rule's right-hand side allowed to have any combination of variables and terminals. We show that every regular grammar is already a context-free grammar, and not necessarily the other way around because we give an example of a CFG for {0^n 1^n : n at least 0}, which is not regular. We then make a CFG for the language of palindromes over {0,1}.

What is a context-free grammar? It is a set of 4 items: a set of "variables," a set of "terminals," a "start variable," and a set of rules. Each rule must involve a single variable on its "left side", and any combination of variables and terminals on its right side.

Timestamps:
0:00 - Intro
0:35 - Grammars (generally)
2:35 - Example grammar that has nonregular language
7:45 - Context-Free Grammar (CFG) definition
11:15 - Example CFG for Palindromes

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 CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.