Past exam question: 2081 Chaitra (Regular), Q3(a)
Open in the Padhaiko appQuestion
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:
- Outer structure: equal count of leading 's and trailing 's ().
- Inner structure: equal count of 's and 's ().
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:
S -> aSd | B; B -> bBc | eps
- S
- ⇒aSdS → aSd
- ⇒aaSddS → aSd
- ⇒aaBddS → B
- ⇒aabBcddB → bBc
- ⇒aabbBccddB → bBc
- ⇒aabbbBcccddB → bBc
- ⇒aabbbcccddB → ε
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.