Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Which of the following languages can be recognized by Pushdown Automata(PDA) but cannot be recognized by Deterministic Finite Automata (DFA)?
(A) L1 = (w∈ {0, 1}*| the length of w is even}
(B) L2 = (w∈ {0, 1}*| the length of w is odd}
(C) L3 = (w∈ (0, 1)*| all 0's come before all I's in w}
(D) L4 = (w∈ {0, 1}*| w contains an equal number of 0's and 1's}
(E) L5 = (w∈ {0, 1}*| all 1's come before all 0's in w}
Choose the correct answer from the options given below:
1
(A) and (B) Only
2
(B) and (C) Only
3
(D) Only
4
(D) and (E) Only