Past exam question: 2082 Kartik (Back), Q3(b)
Open in the Padhaiko appQuestion
Design a PDA for the language that accepts all the string of with and and check the string . Also draw parse tree.
Solution
PDA Design Specification: The language requires:
- At least one followed by at least one .
- The number of 's () is greater than or equal to the number of 's ().
Operational Logic:
- In state , read the first and push onto stack (), guaranteeing .
- In state , push an for each subsequent read ().
- Transition to on the first while popping an (), guaranteeing .
- In state , continue popping an for each read ().
- After all 's are read, if top of stack is (meaning ) or (meaning ), transition on to accept state .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | Z0 | q1 | AZ0 |
| q1 | a | A | q1 | AA |
| q1 | b | A | q2 | ε |
| q2 | b | A | q2 | ε |
| q2 | ε | A | q3 | A |
| q2 | ε | Z0 | q3 | Z0 |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aab
- ✓ accepts aaabb
- ✓ accepts aaaabb
- ✓ accepts aaaaabbb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects abb
- ✓ rejects aabbb
- ✓ rejects bba
Trace for w = aaaaabbb and Parse Tree: Given (, ):
Equivalent Grammar and Parse Tree: A CFG generating is:
For , the parse tree is:
S
/ \
a S
/ \
a S
/ | \
a S b
/|\
a S b
/ \
a bAnswer:
The PDA pushes for each and pops for each . For , the machine consumes all symbols with remaining on stack, transitioning to accept state . The CFG derivation and parse tree confirm membership.