Skip to main content

Define CFG with example

Short answer

A CFG is a 4-tuple (V, Σ, R, S) with variables V, terminals Σ, production rules R of form A→α (A∈V, α∈(V∪Σ)*), and start symbol S. Example: S → aSb | ε generates {aⁿbⁿ | n≥0}.

Define a context free grammar (CFG) along with an example.

Definition

A context-free grammar (CFG) is a 4-tuple

G = (V, Σ, R, S)

  • V: finite set of variables (non-terminals),
  • Σ: finite set of terminals, V ∩ Σ = ∅,
  • R: finite set of productions (rules) of the form A → α, where A ∈ V and α ∈ (V ∪ Σ)*,
  • S ∈ V: the start symbol.

"Context-free" means the left side is always a single variable, so it can be replaced regardless of its neighbours. One step of derivation: if A → γ is a rule, then αAβ ⇒ αγβ. The language is L(G) = { w ∈ Σ* : S ⇒* w }. A language is context-free if some CFG generates it.

Example 1: L = {aⁿbⁿ : n ≥ 0}

G = ({S}, {a, b}, R, S) with R: S → aSb | ε

Derivation of aabb: S ⇒ aSb ⇒ aaSbb ⇒ aabb

        S
      / | \
     a  S  b
      / | \
     a  S  b
        |
        ε

Example 2: palindromes over {a, b}

S → aSa | bSb | a | b | ε. This generates abba (S ⇒ aSa ⇒ abSba ⇒ abba) and ababa.

Example 3: arithmetic expressions

E → E + E | E * E | (E) | id.

Context-free languages include nonregular languages like aⁿbⁿ, so CFGs are strictly more powerful than regular expressions. They are used to define programming-language syntax.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →