Coursify

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

Verified Sources
Sep 12, 2026

Ambiguous Grammar (Definition & Example)

In formal language theory and compiler design, a grammar is called ambiguous if there exists at least one sentence/string in the language for which the grammar can generate more than one distinct parse tree (equivalently: more than one leftmost or rightmost derivation).2

For the question:

“A grammar that produces more than one parse tree for some sentence is said to be
(i) Ambiguous (ii) context free (iii) disambiguous (iv) regular”

the correct choice is (i) Ambiguous, because that is exactly the defining property: “more than one parse tree for some string/sentence.”2

Footnotes

  1. Ambiguous grammar - Defines ambiguous grammar via more than one parse tree/leftmost derivation for some string. ↩ ↩2

  2. Ambiguous grammar - States a CFG is ambiguous if a string has more than one distinct parse tree/derivation. ↩ ↩2

  • Ambiguous grammar.
  • Parse tree.
  • Context-free grammar (CFG).
  • Disambiguation.
  • Regular grammar.

The other options are not about “multiple parse trees”:

  • “context free” describes a grammar class (CFG vs other classes), not whether parses are unique.
  • “disambiguous” is the goal/aftereffect (removing ambiguity), not the standard label in the definition.
  • “regular” is about language type (regular languages), not parse-tree uniqueness.

Formal definition (what the exam statement is paraphrasing)

An ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or more than one parse tree.2
So the phrase “produces more than one parse tree for some sentence” is the same as “there exists a sentence with multiple parse trees.”

Footnotes

  1. Ambiguous grammar - Defines ambiguous grammar via more than one parse tree/leftmost derivation for some string. ↩

  2. Ambiguous grammar - States a CFG is ambiguous if a string has more than one distinct parse tree/derivation. ↩

How to answer the multiple-choice question

  1. 1
    Step 1

    Read the defining property in the question: “more than one parse tree for some sentence.”

  2. 2
    Step 2

    Use the definition: a grammar with a string/sentence that has more than one parse tree is called Ambiguous grammar.2

    Footnotes

    1. Ambiguous grammar - Defines ambiguous grammar via more than one parse tree/leftmost derivation for some string. ↩

    2. Ambiguous grammar - States a CFG is ambiguous if a string has more than one distinct parse tree/derivation. ↩

  3. 3
    Step 3

    Remove options that describe grammar classes (context free, regular) rather than ambiguity (multiple parse trees).

  4. 4
    Step 4

    Choose (i) Ambiguous.

Exam shortcut

If you see “more than one parse tree / more than one leftmost derivation,” the keyword is ambiguous grammar.2

Footnotes

  1. Ambiguous grammar - Defines ambiguous grammar via more than one parse tree/leftmost derivation for some string. ↩

  2. Ambiguous grammar - States a CFG is ambiguous if a string has more than one distinct parse tree/derivation. ↩

Common confusion: derivations vs parse trees

Multiple derivations alone aren’t enough; ambiguity is about multiple distinct parse trees (or equivalently multiple leftmost/rightmost derivations for the same string).

Footnotes

  1. Ambiguous grammar - States a CFG is ambiguous if a string has more than one distinct parse tree/derivation. ↩

Option Diagnosis for the MCQ

How well each option matches the defining property in the question.

From ambiguity to disambiguation (conceptual lifecycle)

Multiple parse trees exist

1. Detect

For some sentence, the grammar yields more than one parse tree.2"

Footnotes

  1. Ambiguous grammar - Defines ambiguous grammar via more than one parse tree/leftmost derivation for some string. ↩

  2. Ambiguous grammar - States a CFG is ambiguous if a string has more than one distinct parse tree/derivation. ↩

Parser ambiguity risk

2. Diagnose

Parsing needs extra mechanisms to decide among alternatives."

Footnotes

  1. Ambiguous Grammar - an overview - Explains ambiguity causes difficulty for parsing because choices are unclear. ↩

Unique parse rule/grammar change

3. Disambiguate

Change grammar or add disambiguation rules to enforce a single parse result."

Quick FAQ

Knowledge Check

Question 1 of 3
Q1Single choice

A grammar that produces more than one parse tree for some sentence is called:

Explore Related Topics

1

Lexical Analysis and the Main Structure Used: Finite Automata

Lexical analysis relies on finite automata—typically deterministic finite automata (DFA)—to recognize token patterns defined by regular expressions.

  • Regular expressions for identifiers, numbers, etc., are converted to NFAs then to a DFA for fast scanning.
  • The DFA processes the source character by character, tracking a single current state and emitting a token at each accepting state.
  • Queues, stacks, and trees support other compiler phases (parsing, AST construction) but are not the primary model for token recognition.
  • Lexers output a stream of tokens that the parser consumes for syntax analysis.
2

Type 2 Grammar (Context-Free Grammar): A Short Note with Formal Meaning and Examples

3

Hierarchy and Power of Bottom-Up Parsers: SLR, LALR, and CLR

Bottom‑up LR parsers form a strict hierarchy of power: LR(0) < SLR < LALR < CLR, with each level able to handle all grammars of the lower levels.

  • SLR uses LR(0) items and resolves conflicts with FOLLOW sets; it is the weakest but simplest LR parser.
  • LALR builds full LR(1) items then merges states that share the same core, keeping the same number of states as SLR while adding look‑ahead precision.
  • CLR (canonical LR) retains all LR(1) states and look‑aheads, giving it the highest grammar coverage at the cost of many more states.
  • Merging CLR states to form LALR can introduce reduce‑reduce conflicts (never shift‑reduce), making LALR strictly less powerful than CLR.
  • In practice, tools like Yacc/Bison prefer LALR because it balances power with manageable memory usage.
Browse all research articles