---
title: "Ambiguity; language of S→SS|a"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:ambiguity-inherent-ssa"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/ambiguity-inherent-ssa
site: BCT Engineering
---

# Ambiguity; language of S→SS|a

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2071 Chaitra
- Video: [Lec-37: Ambiguous vs Unambiguous Grammar with examples | Conversion Ambiguous ➡️ Unambiguous](https://www.youtube.com/watch?v=Ov1N3UJEe28) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/ambiguity-inherent-ssa
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Define ambiguity and inherent ambiguity in a parse tree. For a CFG defined by G = (V, Σ, R, S), V = {S}, Σ = {a}, R = {S → SS; S → a}, obtain the language L(G).

## Short answer

Ambiguity: a string has two or more parse trees. Inherent ambiguity: a language where every CFG is ambiguous. For S → SS | a, L(G) = a⁺ (non-empty strings of a's). The grammar is ambiguous (e.g., aaa has two trees), but the language is not inherently ambiguous (unambiguous grammar S → aS | a exists).

## Answer

#### Ambiguity
A CFG is **ambiguous** if some string in its language has **two or more different parse trees** (equivalently, two different leftmost derivations, or two different rightmost derivations).

Example: E → E + E | E * E | id. The string id + id * id has two parse trees.

#### Inherent ambiguity
A context free **language** is **inherently ambiguous** if **every** CFG that generates it is ambiguous; no unambiguous grammar exists for it. Ambiguity of a grammar can often be removed by rewriting it, but not for inherently ambiguous languages.

Example: L = { aⁱbʲcᵏ : i = j or j = k } is inherently ambiguous. Strings with i = j = k can be generated in both ways in any grammar.

#### Language of G: V = {S}, Σ = {a}, S → SS | a
**Claim: L(G) = { aⁿ : n ≥ 1 } = a⁺.**

- (⊆) Every derived terminal string contains only a's, and S ⇒* ε is impossible since there is no ε-production, so each string has at least one a.
- (⊇) By induction on n. For n = 1: S ⇒ a. If aᵏ ∈ L(G) for all k < n, then for n ≥ 2, S ⇒ SS ⇒* a^(n−1)·a = aⁿ.

So L(G) = a⁺ (any non-empty string of a's).

#### G is ambiguous
The string aaa has two different parse trees:
```text
  (aa)a grouping        a(aa) grouping
        S                    S
       / \                  / \
      S   S                S   S
     / \  |                |  / \
    S   S a                a S   S
    |   |                    |   |
    a   a                    a   a
```
Both trees have yield aaa, so **G is ambiguous**.

However, **L(G) = a⁺ is not inherently ambiguous**, because the unambiguous grammar S → aS | a generates the same language.

## Check yourself

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

1. When is a CFG ambiguous?
   A. It has more than one variable
   B. Some string has two or more different parse trees
   C. It has an ε-production
   D. Its language is infinite
   Answer: B. Ambiguity means a string with multiple parse trees (or leftmost derivations). (Key point: Ambiguous grammar)

2. What is an inherently ambiguous language?
   A. One whose every CFG is ambiguous
   B. One with an ambiguous grammar
   C. A regular language
   D. One with no grammar
   Answer: A. No unambiguous grammar exists for such a language. (Key point: Inherent ambiguity)

3. What is L(G) for S → SS | a?
   A. {aⁿ : n ≥ 0}
   B. {a²ⁿ}
   C. {aⁿ : n ≥ 1} = a⁺
   D. {a}
   Answer: C. There is no ε-rule, so every string has at least one a, and every aⁿ is derivable. (Key point: Language of S → SS | a)

4. Why is a⁺ not inherently ambiguous even though G is ambiguous?
   A. The string aaa has one tree
   B. Because a⁺ is empty
   C. Because G has no start symbol
   D. Because the unambiguous grammar S → aS | a generates it
   Answer: D. An equivalent unambiguous grammar exists, so ambiguity is a property of G only. (Key point: Is a⁺ inherently ambiguous)

## Related in Theory of Computation

- [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×
- [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 palindromes with parse trees](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-palindrome-parse-trees) — 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×
- [CNF: S→aAb|Ba|A, A→SS|ε, B→ε](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-aab-ba) — Theory of Computation, chapter 3