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

https://youtu.be/nagYqfzY2HE?t=4845
video solution
credit - Deepak sir 

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

---

checkout vedio

Option C is correct

Answer 1

Language of above DFA is all strings over $\{0,1\}$ that contain substring $001$.

Regular expression of above DFA is $(0+1)^*00\mathbf{1}(0+1)^*$

$\mathbf{1}$ that is underlined  can not be first bit of $7$-bit binary no, but can be fourth bit or last bit.

Case 1: if it is $4$th bit ,then possible set of strings can be

First $001$ twobits Last   =  $\mathbf{1} 00 \mathbf{1}(00+01+10+11)\mathbf{1} =  4$ strings 

Case 2 : if it is last bit, then possible set of strings can be 

First twobits fourth $001  = \mathbf{1} (00+01+10+11)\mathbf{1} \ 00\mathbf{1} = 4$ strings

String common in both cases $\mathbf{1}00\mathbf{1}00\mathbf{1}$

Total strings $= 4 + 4 - 1 = 7$ strings

Correct Answer: $C$

Comments

nice explanation

---

I agree with this answer, but how did you get (0+1)*001(0+1)*, I can understand it is correct and intuitively it can be obtained, but I couldn't derive it using ardins theorm and I don't think that expression could be simplified unless it is intuitively eliminated
the one I got was (1 + 01)*000*(1+0)*

 

---

1001001 is repeated counted so once its reduced

Answer 2

In this type of question Just write down all the possibilities Speedily and count the correct ones by analyzing the DFA.

See below img .Here we are getting total 7 required Strings.

Comments

reason to cancel other option?

 

---

this is a bad approach of solving this in real exam i mean firstly u need to be carefull to count about recounting the combination.then u need to check them all manually by passing them from DFA i mean even if u miss count just a single string u will be lossing marks and on top of that time.

---

This is not a bad approach at all. Generating the truth table would hardly take ~30s and you don't need to check all the combinations considering how the DFA is accepting the input. If you know what you're doing, this won't take more than 2 mins :)

Answer 3

We will observe the given bit pattern of 7 bit binary string and then try to make it accept.

Given that D1, D4 and D7 are 1.

We will try different combinations of D2 and D3 and on requirement to get the string accepted by machine we'll adjust the D5 D6 bits.

D1	D2	D3	D4	D5	D6	D7	Remarks
1	0	0	1	X	X	1	Case 1
1	0	1	1	0	0	1	Case 2
1	1	0	1	0	0	1	Case 3
1	1	1	1	0	0	1	Case 4

Case 1 : When D2 and D3 are 0 0 : the string starts with 1001 and after that whatever comes will be accepted because 1001 will move to final state. D5 and D6 are marked as Don't Cares as whether they are 0 or 1 it doesn't matter string will get accepted.

So number of combinations for this string?

D5 can take 2 values (0 or 1)

D6 can take 2 values (0 or 1)

total strings for this case which will be accepted : 4

Case 2 : When D2 and D3 are 0  1 : Now D5 and D6 both need to be 0 0 for the string to be accepted.

Number of String for this case - 1

Case 3: When D2 and D3 are 1 0 : Similar to case 2, D5 and D6 both need to be 0 0 for the string to get accepted.

Number of String for this Case : 1

Case 4 : When D2 and D3 are 1 1 : Here also D5 and D6 need to be 0 0 for the string to be accepted.

Number of String for this Case  : 1

Now we have finally exhausted all cases where a 7 bit string can be accepted by this machine M.

Total number of strings :

4+1+1+1=7 Ans(Add up all cases)

Answer 4

option C

the strings are

1>1001001

2>1001011

3>1001101

4>1001111

5>1101001

6>1011001

7>1111001

Answer 5

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.

Comments

simple and straightforward, I like it

Answer 6

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