Correct : a,c,d
The correct answers are Options A, C, and D
Option A — i + k = j + ℓ: This is a linear balance constraint. A PDA can handle it by pushing for every ''''a'''' read, popping for every ''''b'''', pushing for every ''''c'''', and popping for every ''''d''''. The stack is empty at the end iff i − j + k − ℓ = 0, i.e., i + k = j + ℓ. CFL ✓ Correct.
Option B — i = k and j = ℓ: This gives the language {aⁱ bʲ cⁱ dʲ}, which requires two independent cross-serial counts to be matched simultaneously. A single-stack PDA cannot compare both i with k and j with ℓ independently when they interleave. This is a context-sensitive language. Not CFL ✗ Incorrect.
Option C — i = ℓ and j = k: This gives the language {aⁱ bʲ cʲ dⁱ}, which has a perfectly nested structure. A PDA pushes i a''''s, then pushes j b''''s, then pops j for c''''s (matching j = k), then pops i for d''''s (matching i = ℓ). A simple grammar S → aSd | T, T → bTc | ε generates exactly this language. CFL ✓ Correct.
Option D — i + j = k + ℓ: Another linear balance constraint. A PDA pushes for every ''''a'''' and ''''b'''', and pops for every ''''c'''' and ''''d''''. The stack is empty iff i + j = k + ℓ. CFL ✓ Correct.
Similar Questions
Total Unique Visitors