3 3 votes Which of the following languages can be recognized by a Deterministic Finite Automaton? A. The set of binary strings representing odd integers greater than 1 . B. The language $L=\left\{a^{n} b^{2 n} \mid n \geq 0\right\}$. C. The set of unary strings where the length is a prime number. D. The language of palindromic binary strings (strings that read the same forwards and backwards). Theory of Computation goclasses theory-of-computation goclasses-cs-dpp goclasses-cs-dpp-day-111 goclasses-toc-practice-questions + – GO Classes 300 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
0 0 votes B. The language $L=\left\{a^{n} b^{2 n} \mid n \geq 0\right\}$. This is a non-regular, context-free language. A DFA does not have the memory (like a stack) required to count the number of 'a's and ensure the number of 'b's is exactly double that count for an arbitrarily large $n$. C. The set of unary strings where the length is a prime number. This is not a regular language. The gaps between prime numbers are not regular, and a machine with a finite number of states cannot determine if an arbitrarily large number is prime. This can be formally proven using the Pumping Lemma for regular languages. D. The language of palindromic binary strings. This is another classic example of a nonregular, context-free language. To check if a string is a palindrome, a machine needs to remember the first half of the string to compare it with the second half. A DFA has finite memory and cannot do this for strings of arbitrary length. Only A is correct GO Classes answered Oct 16, 2025 GO Classes comment Share Follow 0 reply Please log in or register to add a comment.
