Which of the following set can be recognized by a deterministic finite state…
1998
Which of the following set can be recognized by a deterministic finite state automaton?
- A.
The numbers 1, 2, 4, 2ⁿ written in unary
- B.
The set of binary strings in which the number of zeroes is the same as the number of ones
- C.
The numbers 1, 2, 4, 8, 2ⁿ written in binary
- D.
The set { 1, 101, 11011, 1110111, … }
Attempted by 86 students.
Show answer & explanation
Correct answer: C
A Deterministic Finite Automaton recognizes regular languages. Option C represents binary powers of 2, forming the regular expression 10*, which requires finite memory. Options A, B, and D require counting or tracking unbounded information beyond DFA capabilities.
A video solution is available for this question — log in and enroll to watch it.