Context-Free Grammar — Definition, Formula & Example
A context-free grammar is a finite list of substitution rules that builds strings one step at a time. You start from a single symbol and repeatedly replace a placeholder with a pattern until only actual characters remain.
A context-free grammar is a 4-tuple . Here is a finite set of variables (nonterminals). is a finite set of terminals, disjoint from . is a finite set of rules of the form , where and . is the start variable. The language of is , the set of all terminal strings derivable from . The grammar is called context-free because each rule's left side is a single variable. You may therefore rewrite that variable wherever it appears, regardless of the symbols around it.
Key Formula
Where:
- = Finite set of variables (nonterminals), the placeholders that get replaced
- = Finite set of terminals, the characters that appear in finished strings
- = Finite set of rules, each rewriting one variable as a string of variables and terminals
- = The start variable, where every derivation begins
Worked Example
Problem: Let G have one variable S, terminals a and b, and the two rules S → aSb and S → ab. Show that the string aaabbb is in L(G).
Step 1: Start from S and apply the rule S → aSb. This places one a on the left and one b on the right, with S still in the middle.
Step 2: Apply S → aSb again to the S in the middle. The surrounding symbols do not matter, which is exactly what context-free means.
Step 3: Finish by applying S → ab. No variables remain, so the result is a terminal string with 3 a's followed by 3 b's, a string of length 6.
Answer: Yes. The derivation S ⇒ aSb ⇒ aaSbb ⇒ aaabbb shows that aaabbb is in L(G). This grammar generates exactly the strings made of n a's followed by n b's, for n at least 1. That language is not regular, so no finite automaton can recognize it.
Why It Matters
Compilers use context-free grammars, written in Backus–Naur form, to parse the syntax of languages like Python and C. In a theory of computation course, you will prove that context-free languages are exactly the languages recognized by pushdown automata. In logic, a CFG defines which strings of symbols count as well-formed formulas.
Common Mistakes
Mistake: Assuming any pattern you can describe in words has a context-free grammar.
Correction: Some languages are provably not context-free. One example is n a's, then n b's, then n c's. You can show this with the pumping lemma for context-free languages. Matching two counts is possible, but a CFG cannot keep three counts equal.
