Which of the following languages cannot be accepted by push down automata?…

2026

Which of the following languages cannot be accepted by push down automata?

image.png

Choose the correct answer from the options given below:

  1. A, C & D Only

  2. B, D & E Only

  3. A & B Only

  4. C & D Only

  1. A.

    1

  2. B.

    2

  3. C.

    3

  4. D.

    4

Attempted by 24 students.

Show answer & explanation

Correct answer: C

To determine which languages cannot be accepted by a Push Down Automaton (PDA), we must identify which ones are not Context-Free Languages (CFLs). PDAs accept exactly the class of CFLs.

Analysis of each language:

  • A. L = {a n b n c n : n >= 0}This language requires counting three different symbols and ensuring they are equal. A single stack cannot track three independent counts. This is a classic example of a language that is NOT Context-Free.

  • B. L = {ap : p is Prime}Checking for primality is a complex arithmetic property that cannot be handled by the stack mechanism of a PDA. This language is not Context-Free.

  • C. L = {wcwR : w belongs to {a, b}*.This is a standard Context-Free Language. A PDA can push symbols of w onto the stack, read the center marker c, and then pop symbols to match wR.

  • D. L = {w belongs to {a, b}* : na(w) = nb(w)}. This language requires equal numbers of a's and b's. A PDA can push a's and pop for b's (or vice versa). This is a Context-Free Language.

  • E. L = {a n b m c n+m : n>=0, m>= 0}. This can be generated by a Context-Free Grammar.

Conclusion: Languages A and B are not Context-Free and cannot be accepted by a PDA. Languages C, D, and E are Context-Free.

Therefore, the correct option is 'A & B Only'.

Explore the full course: Mppsc Assistant Professor