Course contentsShow
← Computer Science
Lesson 1816 of 2,87241. Context-Free LanguagesFree lesson

Language Generated by a Grammar

Define the language L(G) as the set of all strings derivable from the start symbol.

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:

  1. Consist only of terminal symbols (no variables left)
  2. 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.