7.1 Context-Free Grammars: Parse Trees, Leftmost & Rightmost Derivations

Back to DBMS Notes

📚Module 01Topic 1.1⏱️18 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The Sentence Blueprint & Branching Tree

In natural language and programming languages alike, sentences are not merely linear streams of beads on a string; they possess deep nested, hierarchical structure.

Regular expressions and finite automata can count modulo a number or verify sequential prefixes, but they are powerless when syntactic structures must nest indefinitely—such as matching parentheses (( ( ) )), matching HTML tags <div><span></span></div>, or evaluating mathematical expressions with operator precedence like (3 + (4 * 5)).

To capture this recursive hierarchy, linguist Noam Chomsky introduced Context-Free Grammars (Type-2). A grammar is called context-free because any syntactic variable (non-terminal) on the left-hand side of a rule can be replaced by its right-hand expansion regardless of what symbols surround it (independent of its linguistic context).

🍳 The Everyday Analogy: The Russian Matryoshka Nesting Doll

Consider a Russian nesting doll (Matryoshka):

• You open the outer doll labeled Doll. Inside, you find another Doll and a small wooden Toy.
• You can write this rule as:

$\text{Doll} \longrightarrow \text{Toy} \quad \text{Doll} \quad \text{Toy} \quad \mid \quad \epsilon$

• If you repeat this replacement three times and terminate with $\epsilon$, you get three layers of matching toys: Toy Toy Toy followed by Toy Toy Toy.
• You do not need to inspect what is outside the doll to open the next layer. The rule applies purely from the inside out.

When you draw the parent-child relationships of how each doll revealed smaller dolls, you obtain a branching tree. The root is the largest doll, the internal branches are intermediate open dolls, and the leaves on the table are the physical toys.

💻 Bridging to Computer Science

In computer science, a Context-Free Grammar (CFG) serves as the formal architectural blueprint for programming language parsers (such as GCC, Clang, V8, and Python's AST parser):

• Lexical Tokens (Terminals $T$): Identifiers, numbers, keywords (if, while), and operators (+, *).
• Syntactic Categories (Variables / Non-Terminals $V$): Expressions, statements, blocks, function declarations.
• Production Rules ($P$): Rewrite specifications that define valid syntactic expansion.

Every valid program is derived through a sequential rewrite process called a derivation:

• Expanding the leftmost variable at every step produces a Leftmost Derivation (LMD) (the foundation of top-down parsers like recursive descent and LL parsers).
• Expanding the rightmost variable at every step produces a Rightmost Derivation (RMD) (the reverse of bottom-up shift-reduce parsers like LR, LALR, and Yacc/Bison).
• The visual geometric representation of this derivation is the Parse Tree (Concrete Syntax Tree), where the left-to-right sequence of leaves forms the final source code string (the yield of the tree).

---

📑Table of Contents

• 🧱 The Formal Definition of a Context-Free Grammar
  • The Defining Constraint of Type-2 Grammars
• 🔀 Derivations & Sentential Forms
  • The Single-Step Yield Relation (⇒)
  • Transitive Closure (⇒*)
  • Sentential Forms vs. Sentences
• 🌲 Leftmost vs. Rightmost Derivations
  • Concrete Walkthrough: Arithmetic Expressions
• 🌳 Parse Trees: The Geometric Hierarchy
  • The Master Theorem of Parse Trees
• 🏭 Real-World Production Context: Compilers & AST Generation
  • Industrial Production Case Studies
• 📐 Numerical Applications & Worked Examples
  • Problem 1: Systematic Derivations & Parse Tree Yield
  • Problem 2: Balanced Parentheses Language & Derivation Trees
  • Problem 3: Palindromes and Derivation Tree Depth Analysis
• 🎯 Exam & Interview Pitfall Check

---

🧱 The Formal Definition of a Context-Free Grammar

A Context-Free Grammar is formally defined as a 4-tuple:

$G = (V, T, P, S)$

The 4 Components of a Context-Free Grammar

Mathematical anatomy of the Type-2 phrase-structure grammar tuple

🔠

Variables / Non-Terminals (V)

Syntactic Categories

• A finite set of placeholder symbols representing abstract syntactic structures.
• Variables can be expanded into other variables and terminals.
• Commonly denoted by uppercase letters: S, A, B, C, E, T, F.

Key Abstractions / Calls

V = {E, T, F}Non-terminal set

🔡

Terminals (T)

Alphabet Symbols

• A finite set of atomic, immutable symbols that form the actual language strings.
• Terminals cannot be replaced or expanded further.
• Commonly denoted by lowercase letters (a, b, c), digits (0, 1), and punctuation.

Key Abstractions / Calls

T = {id, +, *, (, )}V ∩ T = ∅

📜

Production Rules (P)

Rewrite Mappings

• A finite set of rewriting rules of the strict form: A → α.
• LHS must consist of a SINGLE non-terminal: A ∈ V.
• RHS is any finite string of variables and terminals: α ∈ (V ∪ T)*.

Key Abstractions / Calls

A → αα ∈ (V ∪ T)*

🏁

Start Symbol (S)

Root Variable

• A distinguished non-terminal symbol from V: S ∈ V.
• All derivations in the language begin from this single starting point.
• Represents the entire program, document, or sentence.

Key Abstractions / Calls

S ∈ VInitial non-terminal

The Defining Constraint of Type-2 Grammars

What separates a Context-Free Grammar from a Type-1 (Context-Sensitive) or Type-0 (Unrestricted) grammar is the strict structural constraint on the Left-Hand Side (LHS) of every production:

$\underbrace{A}_{\text{Strictly ONE variable } \in V} \longrightarrow \underbrace{\alpha}_{\text{Any string } \in (V \cup T)^*}$

• In a Type-1 Grammar, a production has the form $\alpha A \beta \to \alpha \gamma \beta$, where variable $A$ can only be replaced when flanked by context strings $\alpha$ and $\beta$.
• In a Type-2 CFG, there are no context strings on the LHS. Variable $A$ stands alone. Whether $A$ appears at the start of a line, inside a loop, or deeply nested in an expression, it can freely rewrite to $\alpha$.

---

🔀 Derivations & Sentential Forms

A derivation is a step-by-step sequence of production replacements that starts at the start symbol $S$ and terminates in a string composed entirely of terminals.

The Single-Step Yield Relation (⇒)

Let $\alpha A \beta$ be a string in $(V \cup T)^*$, where $A \in V$. If there exists a production rule $A \to \gamma \in P$, then we say that $\alpha A \beta$ directly derives (or yields) $\alpha \gamma \beta$:

$\alpha A \beta \Longrightarrow \alpha \gamma \beta$

Transitive Closure (⇒*)

• If $\alpha_1 \Rightarrow \alpha_2 \Rightarrow \cdots \Rightarrow \alpha_m$, we say that $\alpha_1$ derives $\alpha_m$ in zero or more steps, denoted:

$\alpha_1 \Longrightarrow^* \alpha_m$

Sentential Forms vs. Sentences

• Sentential Form: Any string $\alpha \in (V \cup T)^*$ such that $S \Rightarrow^* \alpha$. A sentential form may contain both non-terminals and terminals.
• Sentence: A sentential form containing only terminal symbols: $w \in T^*$ such that $S \Rightarrow^* w$.
• Language of a Grammar $L(G)$: The complete set of all sentences derivable from $S$:

$L(G) = \{w \in T^* \mid S \Longrightarrow^* w\}$

A language $L$ is called a Context-Free Language (CFL) if there exists at least one Context-Free Grammar $G$ such that $L = L(G)$.

---

🌲 Leftmost vs. Rightmost Derivations

When a sentential form contains two or more non-terminals, the order in which we choose to expand them determines the derivation path. Two canonical derivation strategies dominate formal language theory and compiler design:

Derivation Duality: Leftmost vs Rightmost

Contrasting the expansion strategies that govern top-down and bottom-up parsing architectures

Top-Down Strategy

Leftmost Derivation (LMD)

👈

Dominant Architecture / DomainPredictive & LL Parsers

• •At every single derivation step, the LEFTMOST non-terminal is chosen for replacement.
• •Generates terminal prefixes from left to right as the derivation progresses.
• •Denoted mathematically by: α ⇒_lm β.
• •Directly mirrors the execution trace of recursive-descent and LL(k) compilers.

"Always expand the variable closest to the front of the input stream."

Bottom-Up Strategy

Rightmost Derivation (RMD)

👉

Dominant Architecture / DomainShift-Reduce & LR Parsers

• •At every single derivation step, the RIGHTMOST non-terminal is chosen for replacement.
• •Generates terminal suffixes from right to left as the derivation progresses.
• •Denoted mathematically by: α ⇒_rm β. Also called the Canonical Derivation.
• •The reverse of an RMD forms the exact shift-reduce sequence executed by LR(k) and LALR parsers.

"Always expand the variable closest to the end of the input stream."

Concrete Walkthrough: Arithmetic Expressions

Consider the standard expression grammar $G$:

$E \longrightarrow E + E \quad \mid \quad E * E \quad \mid \quad \mathbf{id}$

We wish to derive the target terminal string:

$w = \mathbf{id} + \mathbf{id} * \mathbf{id}$

Leftmost Derivation (LMD)

At every step, we underline the leftmost non-terminal and replace it:

$$\begin{aligned} \underline{E} &\Longrightarrow_{lm} \underline{E} + E && (\text{applied } E \to E + E) \\ &\Longrightarrow_{lm} \mathbf{id} + \underline{E} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{lm} \mathbf{id} + \underline{E} * E && (\text{applied } E \to E * E) \\ &\Longrightarrow_{lm} \mathbf{id} + \mathbf{id} * \underline{E} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{lm} \mathbf{id} + \mathbf{id} * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \end{aligned}$$

Rightmost Derivation (RMD)

At every step, we underline the rightmost non-terminal and replace it:

$$\begin{aligned} \underline{E} &\Longrightarrow_{rm} E + \underline{E} && (\text{applied } E \to E + E) \\ &\Longrightarrow_{rm} E + E * \underline{E} && (\text{applied } E \to E * E) \\ &\Longrightarrow_{rm} E + E * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{rm} E + \underline{E} * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{rm} \underline{E} + \mathbf{id} * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \\ &\Longrightarrow_{rm} \mathbf{id} + \mathbf{id} * \mathbf{id} && (\text{applied } E \to \mathbf{id}) \end{aligned}$$

Both derivations produced the exact same string $w$, but through fundamentally different orderings of variable expansions.

---

🌳 Parse Trees: The Geometric Hierarchy

A Parse Tree (also known as a Derivation Tree or Concrete Syntax Tree) is an ordered, rooted, labeled tree that provides an invariant geometric representation of a derivation, filtering out the chronological order of replacement.

The Anatomical Invariants of a Parse Tree

Formal structural conditions defining a valid Type-2 derivation tree

Root Node

The Start Symbol (S)

🌱

The root of the entire tree must be labeled with the grammar start symbol S ∈ V.

Single entry pointLevel 0 of hierarchyRepresents full source construct

↓Downward Expansion via Production Rules

Interior Nodes

Syntactic Variables (Non-Terminals)

🌿

Every internal node must be a variable A ∈ V. If node A has children X₁, X₂, ..., X_k from left to right, then A → X₁ X₂ ... X_k MUST be a valid production in P.

Node labeling ∈ VOrdered childrenExact production matching

↓Base Case Terminations

Leaf Nodes

Terminals or Epsilon (T ∪ {ε})

🍂

Every leaf node is labeled with a terminal symbol a ∈ T or the empty string ε. If a leaf is labeled ε, it must be the solitary child of its parent.

Node labeling ∈ T ∪ {ε}Zero outgoing edgesImmutable atomic tokens

↓Left-to-Right Concatenation

Tree Yield

The Derived Terminal Sentence (w)

🎯

Concatenating all leaf labels from left to right yields the final string w ∈ T* generated by the parse tree.

Yield(Tree) = wLeft-to-right tree walkIdentical for LMD and RMD

The Master Theorem of Parse Trees

Fundamental Theorem: For any context-free grammar $G$ and any string $w \in L(G)$:

1. Every distinct parse tree corresponds to exactly one unique Leftmost Derivation (LMD).
2. Every distinct parse tree corresponds to exactly one unique Rightmost Derivation (RMD).
3. An LMD and an RMD are structurally equivalent if and only if they map to the same parse tree.

Architecture Flow

The Derivation-to-Tree Mapping Pipeline

How different derivation paths converge onto an identical parse tree geometry

👈Leftmost Path

LMD Sequence

Top-down prefix-first replacement order.

→

Structural Abstraction

🌳Geometric Core

Canonical Parse Tree

Hierarchy of parent-child production links invariant to expansion timing.

→

Suffix-First Trace

👉Rightmost Path

RMD Sequence

Bottom-up canonical shift-reduce order.

---

🏭 Real-World Production Context: Compilers & AST Generation

In modern software engineering, raw source code strings cannot be executed directly by hardware. They must first be parsed into an Abstract Syntax Tree (AST), which is directly derived from the CFG parse tree.

Architecture Flow

Production Compiler Pipeline: From Source Code to AST

How industrial compiler frontends transform text streams into actionable execution trees

🔡Lexical Analysis

Lexer / Tokenizer

Scans raw characters via DFA and regex to emit token stream: [KEYWORD_IF, LPAREN, ID, RPAREN].

→

Token Stream

🌳Syntactic Analysis

CFG Parser (Yacc / ANTLR)

Validates token stream against CFG rules via LMD (LL parser) or RMD (LR parser).

→

Concrete Syntax Tree

✂️AST Synthesis

Tree Pruning & Simplification

Eliminates syntactic noise (parentheses, commas, semicolons); preserves operands and operator hierarchy.

→

Clean Execution Tree

⚡Code Generation

LLVM IR / Bytecode

Traverses AST to perform type checking, register allocation, and machine code optimization.

Industrial Production Case Studies

1. JavaScript V8 Engine (Google Chrome / Node.js): When JavaScript code executes, V8's parser uses an LL(k) parser to construct a concrete syntax tree from the ECMA-262 grammar specification. The parser builds a concise AST in memory, which the Ignition interpreter converts into bytecode in under a millisecond.
2. TypeScript Compiler (tsc): TypeScript specifies its formal grammar using a recursive-descent parser (pure LMD). The parser transforms source files into TypeScript AST nodes (ts.Node), allowing the type checker to traverse expressions and enforce interface contracts.
3. Domain-Specific Language (DSL) Parsing (Terraform & SQL): HashiCorp's HCL (HashiCorp Configuration Language) and PostgreSQL's SQL query planner use CFG parsers (Bison / Flex) implementing LALR(1) grammars (RMD in reverse). SQL queries like SELECT a, b FROM users WHERE id = 1 are parsed into query execution plan trees using context-free derivation rules.

---

📐 Numerical Applications & Worked Examples

Problem 1: Systematic Derivations & Parse Tree Yield

Problem Statement:
Consider the Context-Free Grammar $G = (V, T, P, S)$ where:

• $V = \{S, A, B\}$
• $T = \{a, b\}$
• Productions $P$:

$$\begin{aligned} S &\longrightarrow a B \quad \mid \quad b A \\ A &\longrightarrow a \quad \mid \quad a S \quad \mid \quad b A A \\ B &\longrightarrow b \quad \mid \quad b S \quad \mid \quad a B B \end{aligned}$$

Derive the string $w = \mathbf{aaabbabbba}$ by showing:

1. The complete Leftmost Derivation (LMD).
2. The complete Rightmost Derivation (RMD).
3. The formal yield verification of the resulting parse tree.

Step-by-Step Solution:

Step 1: Leftmost Derivation (LMD)

We systematically expand the leftmost non-terminal at every derivation step:

$$\begin{aligned} \underline{S} &\Longrightarrow a \underline{B} && (\text{using } S \to aB) \\ &\Longrightarrow a a \underline{B} B && (\text{using } B \to aBB) \\ &\Longrightarrow a a a B \underline{B} B \dots \text{ (select } B \to b \text{ strategically)} \\ &\Longrightarrow a a a \underline{B} B B && (\text{using } B \to aBB \text{ to obtain third 'a'}) \end{aligned}$$

Let us carefully trace the target string $w = a a a b b a b b b a$:

1. $S \Longrightarrow a \underline{B}$ (matching 1st symbol a)
2. $\Longrightarrow a a \underline{B} B$ (matching 2nd symbol a)
3. $\Longrightarrow a a a \underline{B} B B$ (matching 3rd symbol a)
4. $\Longrightarrow a a a b \underline{B} B$ (using $B \to b$, matching 4th symbol b)
5. $\Longrightarrow a a a b b \underline{B}$ (using $B \to b$, matching 5th symbol b)
6. $\Longrightarrow a a a b b a \underline{B} B$ (using $B \to aBB$, matching 6th symbol a)
7. $\Longrightarrow a a a b b a b \underline{B}$ (using $B \to b$, matching 7th symbol b)
8. $\Longrightarrow a a a b b a b b \underline{S}$ (using $B \to bS$, matching 8th and 9th symbols bb)
9. $\Longrightarrow a a a b b a b b b \underline{A}$ (using $S \to bA$, matching 9th symbol b)
10. $\Longrightarrow a a a b b a b b b a$ (using $A \to a$, matching final symbol a)

All 10 steps replaced strictly the leftmost non-terminal. This proves $w \in L(G)$.

Step 2: Rightmost Derivation (RMD)

We derive the same string $w$ by strictly replacing the rightmost non-terminal:

$$\begin{aligned} S &\Longrightarrow a \underline{B} \\ &\Longrightarrow a a B \underline{B} \\ &\Longrightarrow a a B b \underline{S} \\ &\Longrightarrow a a B b b \underline{A} \\ &\Longrightarrow a a B b b a \\ &\Longrightarrow a a a B \underline{B} b b a \\ &\Longrightarrow a a a B a B \underline{B} b b a \\ &\Longrightarrow a a a B a \underline{B} b b b a \\ &\Longrightarrow a a a B a b b b b a \\ &\Longrightarrow a a a b b a b b b a \end{aligned}$$

Step 3: Yield Verification

Counting the terminal leaves of the parse tree from left to right:

$\text{Leaves} = [a, a, a, b, b, a, b, b, b, a]$

$\text{Yield} = \mathbf{aaabbabbba} = w$

The length $|w| = 10$, and the number of terminal leaves in the parse tree is exactly 10.

---

Problem 2: Balanced Parentheses Language & Derivation Trees

Problem Statement:
The language of well-formed (balanced) parentheses over $\Sigma = \{(, )\}$ is generated by the CFG:

$S \longrightarrow ( S ) \quad \mid \quad S S \quad \mid \quad \epsilon$

For the string $w = \mathbf{()()}$:

1. Construct two distinct leftmost derivations.
2. Determine whether the grammar produces two distinct parse trees for $w$.

Step-by-Step Solution:

Step 1: First Leftmost Derivation (LMD 1)

Expand using the binary split $S \to SS$ first:

$$\begin{aligned} \underline{S} &\Longrightarrow \underline{S} S && (\text{using } S \to SS) \\ &\Longrightarrow ( \underline{S} ) S && (\text{using } S \to (S)) \\ &\Longrightarrow ( \epsilon ) \underline{S} && (\text{using } S \to \epsilon) \\ &\Longrightarrow () ( \underline{S} ) && (\text{using } S \to (S)) \\ &\Longrightarrow () ( \epsilon ) && (\text{using } S \to \epsilon) \\ &\Longrightarrow ()() \end{aligned}$$

Step 2: Second Leftmost Derivation (LMD 2)

Expand using the split $S \to SS$, but decompose the right sibling:

$$\begin{aligned} \underline{S} &\Longrightarrow \underline{S} S && (\text{using } S \to SS) \\ &\Longrightarrow \epsilon \underline{S} && (\text{using } S \to \epsilon \text{ on first variable}) \\ &\Longrightarrow \underline{S} S && (\text{using } S \to SS \text{ on remaining variable}) \\ &\Longrightarrow ( \underline{S} ) S && (\text{using } S \to (S)) \\ &\Longrightarrow () ( \underline{S} ) && (\text{using } S \to \epsilon \text{ then } S \to (S)) \\ &\Longrightarrow ()() \end{aligned}$$

Alternatively, using $S \to SS \to SSS$:

1. $S \Longrightarrow SS \Longrightarrow SSS \dots$
2. In Tree 1, the root splits into $S \to SS$, where the left child produces () and the right child produces ().
3. In Tree 2, the root expands to $S \to SS$, where the left child expands to $SS$ (producing () and $\epsilon$) and the right child produces ().

Step 3: Conclusion

Because the string $w = ()()$ admits more than one distinct parse tree, the grammar is formally ambiguous.

---

Problem 3: Palindromes and Derivation Tree Depth Analysis

Problem Statement:
Consider the standard palindrome CFG over $\{0, 1\}$:

$S \longrightarrow 0 S 0 \quad \mid \quad 1 S 1 \quad \mid \quad 0 \quad \mid \quad 1 \quad \mid \quad \epsilon$

1. Construct the parse tree for the even-length palindrome $w = \mathbf{1001}$.
2. Compute the exact depth of the parse tree and the total number of internal vs. leaf nodes.

Step-by-Step Solution:

Step 1: Derivation Sequence

To generate $w = 1001$:

$$\begin{aligned} S &\Longrightarrow 1 S 1 && (\text{applied } S \to 1S1) \\ &\Longrightarrow 1 0 S 0 1 && (\text{applied } S \to 0S0) \\ &\Longrightarrow 1 0 \epsilon 0 1 && (\text{applied } S \to \epsilon) \\ &= 1001 \end{aligned}$$

Step 2: Parse Tree Topology

• Level 0 (Root): Node $S$
  • Children: Leaf 1 (left), Internal Node $S$ (middle), Leaf 1 (right).
• Level 1 (Middle Child): Node $S$
  • Children: Leaf 0 (left), Internal Node $S$ (middle), Leaf 0 (right).
• Level 2 (Middle Child): Node $S$
  • Children: Single Leaf $\epsilon$.

Step 3: Node Count & Depth Calculation

• Depth of Tree: The longest path from root to leaf is $S \to S \to S \to \epsilon$, which has 3 edges. Depth = 3.
• Internal Nodes:
  • Root $S$ (Level 0)
  • Middle $S$ (Level 1)
  • Deepest $S$ (Level 2)
  • Total internal nodes = 3.
• Leaf Nodes:
  • Terminal 1 (from Level 0)
  • Terminal 0 (from Level 1)
  • Epsilon $\epsilon$ (from Level 2)
  • Terminal 0 (from Level 1)
  • Terminal 1 (from Level 0)
  • Total leaf nodes = 5 ($4$ visible terminals + $1$ empty string marker $\epsilon$).
• Total Nodes in Tree: $3 + 5 = \mathbf{8}$ nodes.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Does every string generated by a CFG have both an LMD and an RMD?
  Yes! If a string $w$ belongs to $L(G)$, there exists at least one derivation tree for $w$. By traversing that derivation tree in pre-order (visiting children left-to-right), you obtain the Leftmost Derivation. By traversing the tree visiting children right-to-left, you obtain the Rightmost Derivation. Every valid sentence has at least one LMD and at least one RMD.
• If a string has two different derivations, does that mean the grammar is ambiguous?
  Not necessarily! A string can have two different derivations simply because one is an LMD and the other is an RMD. That is completely normal! A grammar is ambiguous only if there are two different Leftmost derivations, or two different Rightmost derivations, or two distinct Parse Trees for the same string.
• Can a CFG production have an empty string on the RHS ($A \to \epsilon$)?
  Yes. In a context-free grammar, $A \to \epsilon$ is a valid production (called a null or $\epsilon$-production). However, the left-hand side must strictly be a single non-terminal ($A \in V$). A production like $\epsilon \to A$ or $ab \to \epsilon$ is strictly prohibited in Type-2 grammars.

Common Interview Traps

• Trap: Confusing Abstract Syntax Trees (AST) with Parse Trees (CST):
  A parse tree (CST) contains every single grammar symbol, including punctuation, semicolons, and parentheses that do not hold semantic meaning. An AST discards syntax noise and retains only the operational structure (e.g. operator node + with left child a and right child b).
• Trap: Assuming the Yield Includes Non-Terminals:
  The yield of a parse tree is strictly the concatenation of its leaf nodes. During derivation, intermediate steps are sentential forms; but the final yield of a completed parse tree generating a sentence must consist solely of terminal symbols (and $\epsilon$ markers).
• Trap: Believing LMD and RMD Can Produce Different Strings:
  An LMD and RMD of the same parse tree always yield the exact same terminal string. They differ only in the chronological sequence of node expansion, not in the final sentence generated.

---

🗺️View Complete DBMS Roadmap & Syllabus

← Previous Topic6.3 Decision Algorithms & Closure Property Theorems of Regular LanguagesNext Topic →7.2 Ambiguity in Context-Free Grammars & Inherently Ambiguous Languages