Solution

The correct answer is (D) Only

EXPLANATION:

• L1 = {w ∈ {0, 1}* | the length of w is even}
  • This is a regular language because counting the length of a string modulo 2 can be done using a deterministic finite automaton (DFA). So, L1 can be recognized by a DFA.
• L2 = {w ∈ {0, 1}* | the length of w is odd}
  • This is also a regular language, similar to L1 but for odd-length strings. A DFA can recognize this by keeping track of whether the length is even or odd. So, L2 can be recognized by a DFA.
• L3 = {w ∈ {0, 1}* | all 0's come before all 1's in w}
  • This is a regular language because a DFA can simply switch states when it encounters the first '1' and reject if a '0' appears after a '1'. So, L3 can be recognized by a DFA.
• L4 = {w ∈ {0, 1}* | w contains an equal number of 0's and 1's}
  • This is not a regular language. A DFA cannot count an arbitrary number of 0's and 1's, but a Pushdown Automaton (PDA) can, because a PDA has a stack that can be used to keep track of the number of 0's and 1's. Therefore, L4 can be recognized by a PDA but cannot be recognized by a DFA.
• L5 = {w ∈ {0, 1}* | all 1's come before all 0's in w}
  • This is a regular language, and can be recognized by a DFA for similar reasons as L3 (just reverse the roles of 0's and 1's). So, L5 can be recognized by a DFA.

Thus, the language L4 is the only one that can be recognized by a PDA but not by a DFA, making the correct answer (3) (D) Only.