PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q3(a)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: CFG, Derivations, Parse Trees & Ambiguity

Question

Construct CFG for the language : . Test your grammar to generate and draw parse tree for the same.

Solution

Context-Free Grammar Construction: The language (or ) exhibits nested matching:

We define CFG with production rules:

(If strictly is intended: and ). Here, rule matches 's with 's, and matches 's with 's.

Derivation and Parse Tree for w = aabbbcccdd: For string , the parameters are and ():

Leftmost Derivation:

Leftmost Derivation of aabbbcccddleftmost
S -> aSd | B; B -> bBc | eps
  1. S

Parse Tree Construction:

            S
          / | \
         a  S  d
          / | \
         a  S  d
            |
            B
          / | \
         b  B  c
          / | \
         b  B  c
          / | \
         b  B  c
            |
            ε

Yield: .

Answer:

The CFG is , . Generating requires expanding , matched by the nested parse tree.

All past exam questions for Theory of Computation