PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q7

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: CFG, Derivations, Parse Trees & Ambiguity

Question

Write down the CFG for the language over an alphabet . Use leftmost derivation and right derivation to generate the string "aaaabbcc" and also draw the parse tree for the same.

Solution

Context-Free Grammar Construction: The language consists of two independent concatenated components:

  1. : Every is paired with exactly two 's on the left.
  2. : A non-empty sequence of 's.

We define the CFG with variables , terminals , start symbol , and production rules:

Leftmost and Rightmost Derivations for aaaabbcc (n=2, m=2): To generate the string with and :

Leftmost Derivation (LMD):

Leftmost Derivation of aaaabbccleftmost
S -> XY; X -> aaXb | aab; Y -> cY | c
  1. S

Rightmost Derivation (RMD):

Rightmost Derivation of aaaabbccrightmost
S -> XY; X -> aaXb | aab; Y -> cY | c
  1. S

Parse Tree Construction: The hierarchical parse tree for is constructed as:

           S
         /   \
        X     Y
      / | \ \ | \
     a  a  X b c Y
          /| \   |
         a a  b  c
Reading the leaves from left to right yields: .
Answer:

The CFG is , , . Derivations for yield string with corresponding leftmost/rightmost derivations and hierarchical parse tree.

All past exam questions for Theory of Computation