Question

Let M be a deterministic finite automata as shown below;

Let S denote the set of 7-bit binary strings in which the first, the third and the last bits are 1. The number of strings in S that are accepted by M is equal to_____.

Answer 1

The given DFA represents set of strings not containing
As given
$\frac{1}{b_1}\frac{}{b_2}\frac{1}{b_3}\frac{}{b_4}\frac{}{b_5}\frac{}{b_6}\frac{1}{b_7}$

• $b_2\text{will be}1\Rightarrow \text{1}ways$
• $b_4{b}_5{b}_6\text{can be arranged in}2\times 2\times 2\times =8\text{ways which is not accepted by the DFA.}$

So, right combination = 8 - 5 = 3