Mathwords logoMathwords

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 G=(V,Σ,R,S)G = (V, \Sigma, R, S). Here VV is a finite set of variables (nonterminals). Σ\Sigma is a finite set of terminals, disjoint from VV. RR is a finite set of rules of the form A→wA \to w, where A∈VA \in V and w∈(V∪Σ)∗w \in (V \cup \Sigma)^*. S∈VS \in V is the start variable. The language of GG is L(G)={w∈Σ∗:S⇒∗w}L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w \}, the set of all terminal strings derivable from SS. 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

G=(V,Σ,R,S)G = (V, \Sigma, R, S)
Where:
  • VV = Finite set of variables (nonterminals), the placeholders that get replaced
  • Σ\Sigma = Finite set of terminals, the characters that appear in finished strings
  • RR = Finite set of rules, each rewriting one variable as a string of variables and terminals
  • SS = 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.
S⇒aSbS \Rightarrow aSb
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.
aSb⇒a2Sb2aSb \Rightarrow a^2 S b^2
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.
a2Sb2⇒a3b3a^2 S b^2 \Rightarrow a^3 b^3
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.

Related Terms

  • Conjunction — Its and-connective appears in formula grammar rules
  • Disjunction — Its or-connective is built by a grammar rule
  • Conditional — Implication formulas are generated by a CFG rule
  • Axiom — Start symbol and rules mirror axioms and inference rules
  • Finite — Grammar is defined by a finite list of rules