Language Generated by a Grammar
What you'll learn: You'll understand how to formally define the set of all strings a context-free grammar can produce.
The Core Idea
So far, you've seen that a context-free grammar (CFG) defines production rules and allows you to derive strings starting from a start symbol. But which strings, exactly, belong to the "language" of that grammar?
The language generated by a grammar G, written L(G), is the set of all strings that:
- Consist only of terminal symbols (no variables left)
- Can be derived from the start symbol using the grammar's production rules
Think of the grammar as a recipe book: L(G) is the collection of every finished dish (terminal-only string) you can cook by starting from the main recipe (start symbol) and following the instructions (productions).
Formal Definition
Given a grammar G = (V, Σ, R, S) where:
- V is the set of variables
- Σ is the set of terminals
- R is the set of production rules
- S is the start symbol
We define:
L(G) = { w ∈ Σ | S ⇒ w }**
Translation: L(G) is the set of all strings w made of terminals such that S derives w in zero or more steps.
Example
Consider this grammar:
- S → aSb | ε
Starting from S, you can derive:
- ε (empty string)
- ab
- aabb
- aaabbb
- ...
So L(G) = { aⁿbⁿ | n ≥ 0 } — all strings with equal numbers of a's followed by b's.
Key Takeaway: The language L(G) of a grammar G is precisely the set of all terminal-only strings derivable from the start symbol — it's the complete output your grammar can generate.