GATE CSE 2003 | Question: 50

Question

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$

Comments

All gates questions are already solved, don't upload it again.

---

Breaking down it into simple terms

it is like 1 _ _ 1 _ _ 1  here first, 4 ^th and  7 ^th  bits are one now the DFA  needs 001 to goto final state  so between these blanks in the first set of blanks or next set of blanks we should fill 00  

Let’s say we did fill 00  in the first set of blanks to make 001 in DFA  so now the string is 1001 _  _ 1 now for the next set of blanks we have four ways of filling (00,01,10,11) count them 4 ways 

Now  lets say we filled 00 in the second set of blanks in  the same way as the first example  now the string will be like 1 _  _ 1 001  .For the blanks (00,01,10,11) again 4 ways .

Total 8 ways we may think but in the first case we filled 1001 00 1   (00 in the blanks)  now  in the second case  1 00 100 1 .here the string is repeating so  1001001 will only come once making 8-1 =7  ways 

Note:Bold zeros are where we filled 

Option c

---

The regex should be

(1+01)* 00+1(0+1)*

---

code chahie

Answer 1

Regular expression : (1+01)*000*1(0+1)*

they ask: 1_ _1 _ _ 1
 
so possiblities are : from regular expression : 00 must be string
                                    
                                   10 0 1 _ _ 1 ------> 1001 (0+1)*  1
                                               0 0
                                               0 1
                                               1 0
                                               1 1

                                 1 _ _ 1 0 0 1 -------> 1 (1+01)* 1001
                                    1 1 1
                                    1 0 1
                                    0 1 1

there for total : 4+3 = 7 string can be possible.

Answer 2

here you can see there are 4 casses  
case 1) 1 followed by 001--->1001(this takes me to final and after there are four possiblity again and all possiblity will keep me at final

you can see in figure).
case 2 )1followed by 011--->1011 by reading this i will stay at starting  then after only one case that took me to final which is 001

so from here i get one more string which get accepted

case 3) it also gives one valid string
case 4) also gives one valid string 

so totol 7 string are possible.
and you can see in figure

 

Answer 3

Can be easily done via brute force method.

The string is 1_ _ 1_ _ 1. 4 places, 0 or 1 for each. Hence  2⁴ combinations.