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 fourth and the last bits are 1. The number of strings in S that accepted by M is equal to

Answer 1

$\text{The DFA has an unreachable state, so lets first simplify the DFA.}$

$\text{Now we can see that the DFA represents set of strings not containing '101' as a substring.}\text{We have count number of 7 bit binary strings in which the first, 4}{}^{th}\text{and 7}{}^{th}\text{bits is '1', which go to the}\text{accepting state of DFA.}1\_\_1\_\_1b_1{b}_2{b}_3{b}_4{b}_5{b}_6{b}_7(b_2,b_3)\text{can be either (0,0) or (1,1)}Rightarrow\text{2 ways}(b_5,b_6)\text{can be either (0,0) or (1,1)}Rightarrow\text{2 ways}\text{Total number of ways}=2\times 2=4\text{so there are 4 strings which will be accepted by M.}$