PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q3(b)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: Pushdown Automata, CFG↔PDA & Context-Sensitive Grammar

Question

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:

Operational Logic:

  1. In state , read the first and push onto stack (), guaranteeing .
  2. In state , push an for each subsequent read ().
  3. Transition to on the first while popping an (), guaranteeing .
  4. In state , continue popping an for each read ().
  5. After all 's are read, if top of stack is (meaning ) or (meaning ), transition on to accept state .
PDA for aᵐ bⁿ with m ≥ n > 0PDA
PDA for aᵐ bⁿ with m ≥ n > 0 b,A/ε a,A/AA a,Z0/AZ0 b,A/ε ε,A/A ε,Z0/Z0 q0 q1 q2 q3
StateInputPopNext StatePush
→q0aZ0q1AZ0
q1aAq1AA
q1bAq2ε
q2bAq2ε
q2εAq3A
q2εZ0q3Z0
  • 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   b
Answer:

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.

All past exam questions for Theory of Computation