---
title: "Define CFG with example"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfg-define-example"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-define-example
site: BCT Engineering
---

# Define CFG with example

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2072 Chaitra; 2072 Kartik (asked 2 times)
- Video: [Definition of CFG with an Example || Context Free Grammar || TOC || Theory of Computation|| FLAT| CD](https://www.youtube.com/watch?v=JxRWgobTYto) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-define-example
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Define a context free grammar (CFG) along with an 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}.

## Answer

#### 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

```text
        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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What are the four components of a CFG G = (V, Σ, R, S)?
   A. States, alphabet, transitions, start state
   B. Variables, terminals, productions, start symbol
   C. Variables, stack symbols, transitions, final states
   D. Terminals, tape symbols, rules, blank
   Answer: B. V is variables, Σ terminals, R productions and S the start symbol. (Key point: CFG 4-tuple)

2. Why is the grammar called context-free?
   A. It has no terminals
   B. It cannot generate recursion
   C. The left side of every production is a single variable, replaceable regardless of neighbours
   D. The strings have no context
   Answer: C. Every rule is A → α with a single variable on the left, so it applies regardless of surrounding symbols. (Key point: Meaning of context-free)

3. Which grammar generates {aⁿbⁿ : n ≥ 0}?
   A. S → aS | bS
   B. S → aSb | ε
   C. S → SS | ab
   D. S → Sab | ε
   Answer: B. Each use of S → aSb adds a matching a and b; S → ε ends it. (Key point: Example aⁿbⁿ)

4. Why are CFGs more powerful than regular expressions?
   A. They can generate nonregular languages such as aⁿbⁿ
   B. They use fewer symbols
   C. They need no start symbol
   D. They accept only finite languages
   Answer: A. CFLs include nonregular languages like aⁿbⁿ, so they strictly contain the regular languages. (Key point: Power of CFGs)

## Related in Theory of Computation

- [Unrestricted grammar; superset of CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aunrestricted-grammar-explain) — Theory of Computation, chapter 4, asked 2×
- [CFG versus unrestricted grammar](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-vs-unrestricted-grammar) — Theory of Computation, chapter 4
- [Role of parse tree in CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aparse-tree-role) — Theory of Computation, chapter 3
- [CFG for aᵐbⁿ with m ≥ n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-am-bn-m-ge-n) — Theory of Computation, chapter 3, asked 2×
- [CFG for aⁿb^(2n); parse tree](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-an-b2n-parse-tree) — Theory of Computation, chapter 3, asked 2×
- [CNF conversion (grammar with S→A|B)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-s-a-b) — Theory of Computation, chapter 3

## Related in other subjects

- [Context-sensitive, context-free, regular grammars](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-types-context-sensitive-free-regular) — Discrete Structure, chapter 2