Consider the following Deterministic Finite Automaton M. ISRO 2014 Let S…

Concept: A DFA accepts a string exactly when, starting from the start state and following the transition function symbol by symbol in order, the last symbol leaves the machine in an accepting (final) state. Because a DFA has exactly one outgoing edge per symbol from every state, each string traces a single, unique path through the states, so acceptance is decided purely by that trace, not by any shortcut pattern-matching rule.

Application: Label the five states of M left to right as q0 (start) through q4 (the double circle, accepting), and read the transition function off the diagram:

The set S consists of eight-bit strings b1b2...b8 with b2 = b3 = b6 = b7 = 1 fixed; the remaining four bits b1, b4, b5, b8 are free, giving 24 = 16 candidate strings of the form b1 1 1 b4 b5 1 1 b8. Tracing each of the sixteen combinations through the transition table above gives:

Cross-check: Re-tracing the accepting cases independently, symbol by symbol, confirms the table above:

1. 01110110: q0 -0→ q1 -1→ q2 -1→ q1 -1→ q2 -0→ q3 -1→ q4 -1→ q4 -0→ q4 — ends in the accepting state.

2. 01110111: q0 -0→ q1 -1→ q2 -1→ q1 -1→ q2 -0→ q3 -1→ q4 -1→ q4 -1→ q4 — also ends in the accepting state, confirming that once the machine reaches q4, the last free bit (0 or 1) does not leave it.

3. 01100110 (a rejected case from the table, for contrast): q0 -0→ q1 -1→ q2 -1→ q1 -0→ q0 -0→ q1 -1→ q2 -1→ q1 -0→ q0 — ends back at q0, confirming it is correctly excluded.

Result: Exactly two of the sixteen strings in S — 01110110 and 01110111 — are accepted by M, so the number of strings in S accepted by M is 2.