---
title: "CFG versus unrestricted grammar"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:cfg-vs-unrestricted-grammar"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-vs-unrestricted-grammar
site: BCT Engineering
---

# CFG versus unrestricted grammar

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2071 Chaitra
- Video: [(Part 1) Grammar(Regular,CFG,CSG,Unrestricted), Chomsky Hierarchy with subtitles](https://www.youtube.com/watch?v=UcBkre9t3Lw) — Your Exam Buddy
- 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-vs-unrestricted-grammar
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

What is the difference between a CFG and an unrestricted grammar? Give an example.

## Short answer

CFG rules have a single variable on the left (A→α). Unrestricted grammar allows any non-empty string containing at least one variable (α→β). CFGs generate context-free languages like aⁿbⁿ; unrestricted grammars generate recursively enumerable languages like aⁿbⁿcⁿ with rules such as CB→BC.

## Answer

A **context free grammar (CFG)** has productions A → α, where the left side is a **single variable** and α is any string of terminals and variables. An **unrestricted grammar** (Type 0) has productions α → β, where α is any non-empty string containing at least one variable, and β is any string.

| Point | CFG | Unrestricted grammar |
|---|---|---|
| Left side of rule | exactly one variable | any string with at least one variable |
| Rule form | A → α | α → β |
| Context | replacement independent of context | replacement may depend on neighbours |
| Language class | context free languages | recursively enumerable languages |
| Machine | pushdown automaton | Turing machine |
| Shrinking the string | only by A → ε (one variable erased at a time) | any rule with β shorter than α, so strings can grow and shrink freely |
| Parse tree | exists for every derivation | does not exist in general |
| Example language | { aⁿbⁿ } | { aⁿbⁿcⁿ } |

#### Examples
- **CFG** for { aⁿbⁿ : n ≥ 0 }: S → aSb | ε.
- **Unrestricted grammar** for { aⁿbⁿcⁿ : n ≥ 1 }:
```text
S → aSBC | aBC
CB → BC
aB → ab    bB → bb
bC → bc    cC → cc
```
The rule CB → BC has a left side of two symbols, which no CFG allows. Every CFG is an unrestricted grammar, but not the other way round, since { aⁿbⁿcⁿ } is not context free.

## Check yourself

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

1. What is the key difference between the productions of a CFG and an unrestricted grammar?
   A. CFG left side is exactly one variable; unrestricted allows any string with at least one variable
   B. CFG allows terminals on the left
   C. Unrestricted grammars have no variables
   D. CFG productions must be longer
   Answer: A. CFG: A -> alpha. Unrestricted: alpha -> beta with alpha containing a variable. (Key point: Left side)

2. Which pairing of grammar and language class is right?
   A. CFG: recursively enumerable; unrestricted: context free
   B. CFG: context free; unrestricted: recursively enumerable
   C. CFG: regular; unrestricted: context free
   D. Both generate regular languages
   Answer: B. CFGs generate CFLs (PDA), unrestricted grammars generate RE languages (TM). (Key point: Language classes)

3. Which language needs an unrestricted grammar rather than a CFG?
   A. a^n b^n
   B. a^n b^n c^n
   C. a*
   D. balanced parentheses
   Answer: B. a^n b^n c^n is not context free; rule CB -> BC has a two-symbol left side. (Key point: Example)

4. How does replacement differ?
   A. CFG replacement depends on neighbours; unrestricted does not
   B. CFG replacement is independent of context; unrestricted may depend on neighbours
   C. Both depend on context
   D. Neither depends on context
   Answer: B. A single-variable left side is replaced regardless of context, while longer left sides give context dependence. (Key point: Context)

## 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×
- [Define CFG with example](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-define-example) — Theory of Computation, chapter 3, asked 2×
- [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×