Past exam question: 2082 Chaitra (Regular), Q7
Open in the Padhaiko appQuestion
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:
- : Every is paired with exactly two 's on the left.
- : A non-empty sequence of 's.
We define the CFG with variables , terminals , start symbol , and production rules:
- Rule enforces the base case , and recursively adds two 's and one ().
- Rule enforces the base case , and recursively produces copies of .
Leftmost and Rightmost Derivations for aaaabbcc (n=2, m=2): To generate the string with and :
Leftmost Derivation (LMD):
S -> XY; X -> aaXb | aab; Y -> cY | c
- S
- ⇒XYS → XY
- ⇒aaXbYX → aaXb
- ⇒aaaabbYX → aab
- ⇒aaaabbcYY → cY
- ⇒aaaabbccY → c
Rightmost Derivation (RMD):
S -> XY; X -> aaXb | aab; Y -> cY | c
- S
- ⇒XYS → XY
- ⇒XcYY → cY
- ⇒XccY → c
- ⇒aaXbccX → aaXb
- ⇒aaaabbccX → aab
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.