Which of the following sets can be recognized by a Deterministic Finite-state…
1998
Which of the following sets can be recognized by a Deterministic Finite-state Automaton?
- A.
The numbers 1, 2, 4, 8, ..., 2^n, ... written in binary.
- B.
The numbers 1, 2, 4, 8, ..., 2^n, ... written in unary.
- C.
The set of binary strings in which the number of zeros is the same as the number of ones.
- D.
The set {1, 101, 11011, 1110111, ...}.
Attempted by 51 students.
Show answer & explanation
Correct answer: A
A DFA recognizes exactly the regular languages. Option A gives the binary representations of powers of 2: 1, 10, 100, 1000, and so on. This is the regular language described by 10*, so a DFA can accept it. Option B gives unary strings whose lengths are powers of 2, which is not regular because finite memory cannot test whether the length is a power of 2. Option C needs unbounded counting to compare the number of zeros and ones, so it is not regular. Option D has a matching pattern around the 0, like 101, 11011, 1110111, and so on, which also needs unbounded memory. Therefore, only option A can be recognized by a DFA.