PadhaikoAll subjects

CFG, Derivations, Parse Trees & Ambiguity

Theory of Computation (ENCT 203)

Open in the Padhaiko app

Context-Free Grammar, Derivations, Parse Trees and Ambiguity

In formal language theory, regular expressions and finite automata can describe many simple patterns, but they fail to capture recursive, nested structures such as balanced parentheses or matching counts (e.g., ). Context-free grammars (CFGs) provide a richer, more powerful generative mechanism capable of describing hierarchical block structure, nested syntax, and arithmetic expressions essential for compiler construction.


3.1 Introduction to Context-Free Grammar (CFG) and Context-Free Language

Consider the regular expression , which denotes all strings over beginning with and ending with . Using production rules with a start non-terminal and an auxiliary non-terminal , we can generate this language via:

To generate the string , we substitute by , regardless of the symbols surrounding . Because production replacements depend solely on the single variable being replaced and not on surrounding contextual symbols, the system is termed context-free.

Definition

Context-Free Grammar (CFG)

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

where:

(Note: Some texts denote the total alphabet as and write rules as , treating as non-terminals and as terminals).

Applications of Context-Free Grammars

  1. Compilers and Parsing: CFGs serve as the mathematical foundation for syntactic analysis in modern compilers (such as GCC, Clang, and javac).
  2. Programming Language Specification: The syntax of programming languages (blocks, control flow, functions) is formally specified using CFGs.
  3. Parser Generation: Grammars are directly converted by parser generators (like Yacc, Bison, and ANTLR) into syntax tree builders.
  4. Document Type Definitions: XML DTDs and schema validators define valid nesting of tags through context-free rules.

3.1.1 Terminologies: Derivations, Languages & Sentential Forms

Definition

Derivations, Context-Free Language, and Sentential Forms

Let be a context-free grammar:

  1. Derivation Step (): If , and , then replacing yields .
  2. Derivation (): The reflexive, transitive closure of . If , we write .
  3. Sentential Form: Any string such that . If (contains only terminals), it is called a sentence.
  4. Context-Free Language (): The set of all terminal strings generated from the start symbol:

Worked Out Examples: Designing CFGs

Example 1

1

Let where , , and rules are:

Find the context-free language .

Base String Derivation

Applying the terminal production :

Recursive Substitution

Applying the recursive production once followed by :

Applying repeatedly times followed by :

Answer:

The language generated by grammar consists of all non-empty strings of matching 's and 's:

Example 2

2

Let where , , and production rules:

Find the context-free language .

Derivation Analysis

The base production gives:

Each application of prepends two 's before :

Answer:

The language generated by grammar is:

Example 3

3

Write a Context-Free Grammar for the language:

Analyzing the Condition

The condition means the number of leading 's is greater than or equal to the number of trailing 's. We can decompose this into two phases:

  1. Matching pairs of and ().
  2. Surplus leading 's ( where ).
Formulating the Grammar Productions

Let generate either a balanced and , an extra leading , or terminate at :

Answer:

The CFG is with productions:

Example 4

4

Write a CFG for the language:

Grammar Formulation

A string with equal numbers of 's and 's can be empty (), or start with and end with , or start with and end with , or be the concatenation of two balanced substrings ():

Answer:

The context-free grammar is with rules:

Example 5

5

Write Context-Free Grammars for each of the following languages over :

  1. (odd-length palindromes with center marker )
  2. (even-length palindromes)
Odd-Length Palindromes ()

Matching outer symbols symmetrically until reaching the center terminal or :

Even-Length Palindromes ()

Matching outer symbols symmetrically until shrinking to the empty string:

Strings of Even Length ()

Every step adds any combination of two terminal symbols, ending at :

Strings of Odd Length ()

Symmetrically adding pairs of symbols and ending at a single terminal or :

Answer:

The CFG production sets are:


3.2 Types of Derivations, Parse Trees & Ambiguity

Definition

Leftmost and Rightmost Derivations

  1. Leftmost Derivation (): A derivation in which the leftmost non-terminal variable in the current sentential form is replaced at every single step.
  2. Rightmost Derivation (): A derivation in which the rightmost non-terminal variable in the current sentential form is replaced at every single step.
Definition

Parse Tree (Derivation Tree)

An ordered tree representing the hierarchical syntactic structure of a derivation in grammar :

Example 6

6

Let be the grammar for balanced parentheses:

Show the leftmost derivation, rightmost derivation, and draw the parse tree for the string:

Leftmost Derivation

Expanding the leftmost non-terminal variable at each step:

Leftmost Derivation of (())()leftmost
S → SS | (S) | ε
  1. S
Rightmost Derivation

Expanding the rightmost non-terminal variable at each step:

Parse Tree Construction

The hierarchical parse tree for :

Parse Tree for (())() S S ( S ( S ε ) ) S ( S ε )
Parse Tree for (())() · S → SS | (S) | ε
Answer:

The string has identical yield in both leftmost and rightmost derivations, correctly captured by the derivation tree.

Example 7

7

Let with production rules:

Show the leftmost and rightmost derivations and draw the parse tree for the string .

Leftmost Derivation

Expanding variables from left to right:

Rightmost Derivation

Expanding variables from right to left:

Parse Tree
Parse Tree for abbc S A a A ε B b B b B ε C c C ε
Parse Tree for abbc · S → ABC; A → aA | ε; B → bB | ε; C → cC | ε
Answer:

The derivations yield via , , and .

Example 8

8

Using the balanced parentheses grammar:

Derive the string and construct its parse tree.

Derivation Steps
Parse Tree
Parse Tree for ()() S S ( S ε ) S ( S ε )
Parse Tree for ()() · S → SS | (S) | ε
Answer:

The string is generated by splitting and closing both child clauses using .

Example 9

9

Capture the arithmetic expression using a Context-Free Grammar and draw its parse tree.

Designing the Grammar

Let where:

Derivation and Parse Tree

Deriving the expression with multiplication at the root level to match the grouping:

Parse Tree for (x1 + x2) * x3 S S ( S S x1 + S x2 ) * S x3
Parse Tree for (x1 + x2) * x3 · S -> ( S ) | S + S | S * S | x1 | x2 | x3
Answer:

The production set generates reflecting parenthesis grouping first, followed by outer multiplication.


3.2.3 Ambiguity in CFG

Definition

Ambiguity and Inherent Ambiguity

  1. Ambiguous Grammar: A context-free grammar is called ambiguous if there exists at least one string that possesses two or more distinct parse trees (or equivalently, two or more distinct leftmost derivations, or two or more distinct rightmost derivations).
  2. Inherent Ambiguity: A context-free language is said to be inherently ambiguous if every grammar that generates is ambiguous. A classic example is:
Example 10

10

Demonstrate that the following grammar is ambiguous for the string :

Leftmost Derivation 1 (via S → AB)

Deriving via groups 's with 's and 's with 's ( and ):

Leftmost Derivation 1 for aabbccddleftmost
S → AB | C; A → aAb | ab; B → cBd | cd; C → aCd | aDd; D → bDc | bc
  1. S
Leftmost Derivation 2 (via S → C)

Deriving via groups outer 's with 's and inner 's with 's ( and ):

Leftmost Derivation 2 for aabbccddleftmost
S → AB | C; A → aAb | ab; B → cBd | cd; C → aCd | aDd; D → bDc | bc
  1. S
Parse Tree Comparison

Because there are two distinct leftmost derivations for the string , the grammar produces two distinct parse trees.

First Parse Tree for aabbccdd S A a A a b b B c B c d d
First Parse Tree for aabbccdd · S → AB | C; A → aAb | ab; B → cBd | cd; C → aCd | aDd; D → bDc | bc
Answer:

Since the terminal string admits two distinct leftmost derivations and parse trees, the grammar is ambiguous.


3.3 Regular Grammars

Definition

Regular Grammar

A grammar is called a regular grammar if each production has at most one non-terminal on its right-hand side, placed strictly at the end or beginning:

  1. Right-Linear Grammar: Every rule has the form or , where and .
  2. Left-Linear Grammar: Every rule has the form or , where and .

Every regular grammar generates a regular language and can be transformed into an equivalent Finite Automaton.

Example 11

11

Convert the following right-linear regular grammar into an equivalent Finite Automaton:

State and Transition Construction

Each non-terminal variable corresponds to a state in the automaton:

  • is the start state.
  • is an intermediate state.
  • A new final state is introduced for terminal-only rules:
    • (accepting)
    • (accepting)
Automaton Representation
NFA for Regular GrammarNFA
NFA for Regular Grammar 0, 1 0 1 1 0 S A F
State01
→S{S}{A, F}
A{A, F}{A}
*F∅∅
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 00110
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 11
Answer:

The resulting NFA has states , start state , and accepting state .

Example 12

12

Construct the leftmost derivation, rightmost derivation, and parse tree for the string using the grammar where:

Leftmost Derivation
Rightmost Derivation
Parse Tree

Both leftmost and rightmost derivations produce the identical derivation tree.

Parse Tree for 001001100 S 0 A S 0 A 1 0 S 0 1 A 1 0 S 0
Parse Tree for 001001100 · S -> 0 A S | 0; A -> S 1 A | S S | 1 0
Answer:

The string is successfully derived with identical parse tree structure across leftmost and rightmost expansions.


Solutions to Important Examination Questions

Example 13

13

Construct a context-free grammar for the language:

over . Derive the string and draw its corresponding parse tree. [2082 Baishakh]

Grammar Construction

The condition with requires strictly more 's than 's. The minimal valid string is . We decompose the grammar into balanced 's and 's generated by , followed by extra trailing 's generated by :

Deriving aaabbbb

Derivation of ():

Parse Tree
Parse Tree for aaabbbb S A a A a A a b b B b b
Parse Tree for aaabbbb · S → AB; A → aAb | a; B → bB | bb
Answer:

The CFG is . String is verified with the parse tree above.

Example 14

14

Construct a CFG for the language:

Test your grammar to generate and draw its parse tree. [2081 Chaitra]

Grammar Formulation

The language has nested dependencies: outer 's match outer 's, while inner 's match inner 's.

  • (matching outer )
  • (matching inner )
Deriving aabbbcccdd

Generating ():

Parse Tree
Parse Tree for aabbbcccdd S a S a X b X b X b c c c d d
Parse Tree for aabbbcccdd · S → aSd | aXd; X → bXc | bc
Answer:

The grammar generates through nested variable expansion.

Example 15

15

Construct a CFG for the palindrome language:

Also use the grammar to derive the string and draw its parse tree. [2076 Ashwin]

Production Rules

The language contains all even-length palindromes over . Each step wraps in matching symbols:

Derivation of abba
Parse Tree
Parse Tree for abba S a S b S ε b a
Parse Tree for abba · S → aSa | bSb | ε
Answer:

The CFG is . Derivation and parse tree for are established.

Example 16

16

Write a context-free grammar for:

Use leftmost and rightmost derivations to generate and draw its parse tree. [2075 Chaitra]

Grammar and Leftmost Derivation

Production rules: .

Leftmost derivation for :

Rightmost Derivation

For this sequence of single-variable expansions, the rightmost derivation proceeds through the exact same sentential forms:

Parse Tree
Parse Tree for aababb S a S a S b S ε a b b
Parse Tree for aababb · S → aSb | bSa | SS | ε
Answer:

The grammar generates through symmetric pairing with derivation tree shown above.

Example 17

17

Write a context-free grammar for:

over . Use leftmost and rightmost derivations to generate and draw its parse tree. [2075 Ashwin]

Grammar Formulation

The number of leading 's equals the number of trailing 's (), while intermediate 's () are independent:

Derivations

Leftmost derivation:

Because only one variable exists at each intermediate stage, the rightmost derivation is identical.

Parse Tree
Parse Tree for aabbbcc S a S a A b A b A b c c
Parse Tree for aabbbcc · S → aSc | aAc; A → bA | b
Answer:

The grammar successfully generates .

Example 18

18

Write a CFG for all palindromes over and draw parse trees for an even-length and an odd-length palindrome. [2073 Chaitra]

Grammar Formulation

Palindromes can be even-length (terminating in ) or odd-length (terminating in or ):

Even Palindrome Derivation: abba
Parse Tree for Even Palindrome abba S a S b S ε b a
Parse Tree for Even Palindrome abba · S → aSa | bSb | a | b | ε
Odd Palindrome Derivation: ababa
Parse Tree for Odd Palindrome ababa S a S b S a b a
Parse Tree for Odd Palindrome ababa · S → aSa | bSb | a | b | ε
Answer:

The CFG generates all palindromes. The even palindrome terminates on , while the odd palindrome terminates on .

Example 19

19

Construct a CFG for . Generate the string and construct its parse tree. [2073 Shrawan]

Grammar Design

For each generated on the left, exactly two 's must be generated on the right:

(or for )

Deriving aabbbb

Using :

Parse Tree
Parse Tree for aabbbb S a S a S ε b b b b
Parse Tree for aabbbb · S → aSbb | ε
Answer:

The grammar generates with the parse tree above.

Example 20

20

Write a CFG for the regular expression:

[2072 Chaitra]

Decomposing the Regular Expression

The expression is a concatenation of three parts:

  1. : zero or more 's (represented by variable ).
  2. : a single (represented by variable ).
  3. : any string over (represented by variable ).
Writing the Production Rules
Answer:

The required context-free grammar is:


Exercise Set: CFG, Derivations and Ambiguity

Exercise Questions: CFG, Derivations & Ambiguity

Question 1

Formally define a Context-Free Grammar (CFG). [2082 Baishakh, 2080 Baishakh]

Formal 4-Tuple Specification: A Context-Free Grammar (CFG) is formally defined as a 4-tuple:

where:

  1. is a finite, non-empty set of variables (also called non-terminals or syntactic categories). Each variable defines a sub-language.
  2. is a finite set of terminal symbols (the alphabet of the generated language), disjoint from ().
  3. is a finite set of production rules (rewrite rules). Each production has the form:

The left-hand side contains exactly one variable , and the right-hand side is a string of terminals and/or variables (including the empty string ).

  1. is the distinguished start symbol from which all derivations initiate.

The grammar is called context-free because replacing non-terminal by depends solely on , without regard to surrounding context symbols.

Derivations and Language Generated: Let . If rule , we write:

denoting that directly derives in one step. The reflexive and transitive closure of is denoted by .

The language generated by , denoted , is the set of all terminal strings derived from start symbol :

A language is a Context-Free Language (CFL) if there exists a CFG such that .

Concrete Example and Derivation: Consider grammar with productions:

To generate the string :

Derivation of aabbleftmost
S → aSb | ε
  1. S
Answer:

A Context-Free Grammar is a 4-tuple where is a finite set of variables (non-terminals), is a finite set of terminal symbols disjoint from , is a finite set of productions of the form (), and is the start symbol. The language generated is .

Question 2

What is inherent ambiguity in a context-free grammar? [2079 Bhadra, 2079 Baishakh]

Definition of Inherent Ambiguity: While ambiguity in a specific CFG can often be eliminated by restructuring production rules (such as enforcing operator precedence), some context-free languages possess no unambiguous grammar whatsoever.

A context-free language is called inherently ambiguous if every context-free grammar that generates (i.e. ) is ambiguous. That is, for every CFG for , there exists at least one string that has two or more distinct parse trees (or distinct leftmost derivations).

Canonical Example: : This language is the union of two simpler context-free languages:

  • (matching 's and 's)
  • (matching 's and 's)

A natural CFG generating is:

Two Distinct Leftmost Derivations for :

The string belongs to both and , yielding two distinct parse trees:

  1. Derivation 1 (via , grouping 's and 's first):
  1. Derivation 2 (via , grouping 's and 's first):

Because every CFG generating must generate strings of with multiple parse trees, the language is inherently ambiguous.

Answer:

A context-free language is inherently ambiguous if every context-free grammar that generates is ambiguous (i.e., every possible grammar for yields at least two distinct parse trees for some string ). An example is , where every string of the form inevitably has two independent derivations.

Question 3

What is ambiguity in a Context-Free Grammar? [2078 Kartik]

Definition of Grammar Ambiguity: A Context-Free Grammar is called ambiguous if there exists at least one string for which there are:

  1. Two or more distinct parse trees (derivation trees), or equivalently
  2. Two or more distinct leftmost derivations, or
  3. Two or more distinct rightmost derivations.

If every string in has exactly one unique parse tree, the grammar is unambiguous.

Demonstration on Arithmetic Expressions: Consider the standard expression grammar :

For the input string , two distinct leftmost derivations exist:

  1. Leftmost Derivation 1 (evaluating at root, giving higher precedence):
Leftmost Derivation 1leftmost
E → E + E | E * E | id
  1. E
  1. Leftmost Derivation 2 (evaluating at root, giving higher precedence):
Leftmost Derivation 2leftmost
E → E + E | E * E | id
  1. E

Significance and Disambiguation: Ambiguity creates semantic uncertainty in compiler design because different parse trees correspond to different abstract syntax trees (e.g. vs ).

To remove ambiguity, the grammar is stratified into levels that enforce operator precedence and associativity:

In this unambiguous grammar, multiplication binds tighter than addition , and both operators are left-associative, yielding a unique parse tree for every valid expression.

Answer:

A CFG is ambiguous if there exists at least one terminal string in its language that has two or more distinct parse trees, or equivalently two or more distinct leftmost (or rightmost) derivations. Ambiguity can often be eliminated by structuring production rules to enforce operator precedence and associativity.

Past exam questions for Theory of Computation

← Closure Properties, Pumping Lemma & Decision AlgorithmsSimplification of CFG; CNF, GNF & BNF →