Context-Free Grammars (CFG)

A CFG is a 4-tuple G = (V, T, P, S): variables, terminals, productions of the form A → α, and a start symbol S.

Examples

Text

L = {aⁿbⁿ | n ≥ 0}                 S → aSb | ε
Palindromes over {a, b}            S → aSa | bSb | a | b | ε
Balanced parentheses               S → (S) | SS | ε
Equal numbers of a's and b's       S → aSbS | bSaS | ε

Derivations and Parse Trees

Text

Grammar: E → E + E | E * E | (E) | id
Leftmost derivation of id + id * id:
E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

Ambiguity

A grammar is ambiguous if some string has two or more parse trees (equivalently, two leftmost derivations). The grammar above is ambiguous:

Text

Tree 1:       E                 Tree 2:        E
            / | \                              / | \
           E  +  E                           E  *  E
           |   / | \                       / | \   |
          id  E  *  E                     E  +  E  id
              |     |                     |     |
             id    id                    id    id
      id + (id * id)                   (id + id) * id

Fix it by encoding precedence and associativity: E → E + T | T, T → T * F | F, F → (E) | id.

Simplification

Remove (in this order) ε-productions, unit productions (A → B) and useless symbols (non-generating, then unreachable).

Normal Forms

Form	Allowed productions	Use
Chomsky (CNF)	A → BC or A → a	CYK parsing; derivation of length-n string takes 2n − 1 steps
Greibach (GNF)	A → aα (α ∈ V*)	Each step consumes one terminal; PDA construction

Text

Convert S → aSb | ab to CNF:
A → a,  B → b
S → ASB | AB   ⇒   S → AC | AB,  C → SB
CNF:  S → AC | AB,  C → SB,  A → a,  B → b

Closure Properties of CFLs

CFLs are closed under union, concatenation, Kleene star and intersection with a regular language. They are not closed under intersection or complement. For example, {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, which isn't context-free.

Track your progress through the Theory of Computation course

← Prev Next →