CFG Basics

Context-Free Grammars (CFG) Basics

A context-free grammar (CFG) is a formalism for describing the syntax of languages. Unlike regular expressions, CFGs can describe nested structures like balanced parentheses, arithmetic expressions, and programming language syntax. They are more powerful than finite automata.

Formal Definition

A CFG is a 4-tuple G = (V, Σ, R, S), where:

V     — finite set of variables (non-terminals)
Σ     — finite set of terminals (disjoint from V)
R     — finite set of productions (rules)
S ∈ V — start variable

Production format:
  A → α
  where A ∈ V and α ∈ (V ∪ Σ)*

Example — simple grammar for arithmetic expressions:
  V = {E, T, F}
  Σ = {+, *, (, ), id}
  S = E
  R:
    E → E + T | T
    T → T * F | F
    F → ( E ) | id

Derivations

A derivation is a sequence of steps that replaces variables with strings of terminals and variables using the production rules. We start with the start variable S and apply productions until we have only terminals.

Grammar:
  S → aSb | ε

Derivation of "aabb":
  S ⇒ aSb         (using S → aSb)
    ⇒ aaSbb       (using S → aSb)
    ⇒ aabbb? No — let's fix this.

  Actually:
  S ⇒ aSb
    ⇒ aaSbb
    ⇒ aabb        (using S → ε)

Leftmost derivation (always replace leftmost variable):
  S → aSb → aaSbb → aabb

Rightmost derivation (always replace rightmost variable):
  S → aSb → aabb  (replace S → ε first, then... )
  Actually: S → aSb → aabb (replace S with ε)

Language of a Grammar

The language generated by a grammar G, denoted L(G), is the set of all strings of terminals that can be derived from S. A language is context-free if there exists a CFG that generates it.

CFGs are strictly more powerful than regular expressions. The language {0^n 1^n | n >= 0} can be generated by a CFG but not by any regular expression. This is because CFGs can count and match nested structures.

Grammar for {0^n 1^n | n >= 0}:
  S → 0S1 | ε

Derivation of "000111":
  S → 0S1 → 00S11 → 000S111 → 000111

This language is context-free but NOT regular.
No finite automaton can count unbounded pairs.