Consider the following deterministic finite state automaton M. Let S denote…
2003
Consider the following deterministic finite state automaton M.
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is
- A.
1
- B.
5
- C.
7
- D.
8
Attempted by 52 students.
Show answer & explanation
Correct answer: C
The set S consists of seven-bit binary strings where the first, fourth, and last bits are 1. This means the string is of the form 1 _ _ 1 _ _ 1, where each underscore can be either 0 or 1. The number of such strings is 2^4 = 16, since there are four free bits (positions 2, 3, 5, and 6). To find how many of these are accepted by the DFA, we need to simulate each string on the automaton. The correct answer is 7.
A video solution is available for this question — log in and enroll to watch it.