---
title: "Unrestricted grammar; superset of CFG"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:unrestricted-grammar-explain"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/unrestricted-grammar-explain
site: BCT Engineering
---

# Unrestricted grammar; superset of CFG

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2073 Shrawan; 2073 Chaitra (asked 2 times)
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/unrestricted-grammar-explain
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Explain unrestricted grammar with a suitable example. Is unrestricted grammar a superset of context free grammar? Justify.

## Short answer

Unrestricted grammar has productions α → β with α containing at least one variable, no other restrictions. Example: grammar for aⁿbⁿcⁿ with rule CB → BC. Yes, it's a superset of CFG because every CFG production A → β fits the form, so every CFL is generated. The inclusion is proper (e.g., aⁿbⁿcⁿ is not context-free).

## Answer

#### Unrestricted grammar (Type-0 grammar)
An unrestricted grammar is G = (V, T, P, S), where V is the set of variables, T the terminals, S ∈ V the start symbol, and every production has the form

α → β, with α ∈ (V ∪ T)⁺ containing at least one variable, and β ∈ (V ∪ T)*.

There is no restriction on the length or shape of α and β; the left side may be a string of several symbols (so rules can depend on **context**), and β may be shorter than α (erasing rules). L(G) = { w ∈ T* : S ⇒* w }.

Unrestricted grammars generate exactly the **recursively enumerable languages**, the languages accepted by Turing machines.

#### Example: L = { aⁿbⁿcⁿ : n ≥ 1 }
```text
S  → aSBC | aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc
```
Derivation of aabbcc: S ⇒ aSBC ⇒ aaBCBC ⇒ aaBBCC (CB → BC) ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc. The rule CB → BC has a two-symbol left side, so this grammar is not context free (and indeed no CFG exists for L).

#### Is an unrestricted grammar a superset of CFG?
**Yes.** In a CFG every production has the form A → β with A a **single variable**. This satisfies the requirement of an unrestricted grammar (the left side contains at least one variable). So every CFG is already an unrestricted grammar, and every CFL is a Type-0 language.

The inclusion is **proper**: the grammar above generates { aⁿbⁿcⁿ }, which is not context free (by the pumping lemma). Hence

regular ⊂ context free ⊂ context sensitive ⊂ unrestricted (recursively enumerable).

## Check yourself

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

1. What is the form of productions in an unrestricted grammar?
   A. A -> alpha with A a single variable
   B. alpha -> beta with alpha containing at least one variable
   C. A -> aB or A -> a
   D. alpha -> beta with |alpha| <= |beta| only
   Answer: B. Type-0 rules are alpha -> beta where alpha is any non-empty string with at least one variable and beta is any string. (Key point: Production form)

2. What class of languages do unrestricted grammars generate?
   A. Context free languages
   B. Context sensitive languages only
   C. Recursively enumerable languages
   D. Regular languages
   Answer: C. Unrestricted grammars generate exactly the languages accepted by Turing machines, the RE languages. (Key point: Language class)

3. Why is every CFG an unrestricted grammar?
   A. Its rules A -> beta already have a left side with a variable
   B. It has no variables
   C. It has longer left sides
   D. It can use erasing rules only
   Answer: A. A single variable on the left satisfies the 'at least one variable' requirement, so CFG rules are valid Type-0 rules. (Key point: Superset of CFG)

4. Which language shows the inclusion of CFG in unrestricted grammars is proper?
   A. a^n b^n
   B. a^n b^n c^n
   C. a*b*
   D. palindromes
   Answer: B. a^n b^n c^n has an unrestricted grammar but is not context free, by the pumping lemma. (Key point: Proper inclusion)

## Related in Theory of Computation

- [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
- [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×
- [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×

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