in Theory of Computation edited by
14,725 views
61 votes
61 votes

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

  1. $1$
  2. $5$
  3. $7$
  4. $8$
in Theory of Computation edited by
14.7k views

4 Comments

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

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

4
4
The regex should be

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

7 Answers

83 votes
83 votes
Best answer

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$

edited by

4 Comments

how do we simplify your regular expression to the one given by @Praveen Saini 

how is this conversation made?

1* 0(10)* 00* 1 (0+1)*  → (0+1)*001(0+1)*

1
1

how do we simplify your regular expression to the one given by @Praveen Saini 

how is this conversation made?

0
0
code chahie
0
0
97 votes
97 votes

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.

4 Comments

One more way to analyze it.

Bit no 2,3 if 00 then it reaches final state. So when bit 2,3 are 0, bit 5,6 can be anything = 4 strings.

If bit 2,3 are anything other than 00, we come back to start state and only 00 from bit 5,6 can take us to final state. So with 01,10,11 of bit 2,3 we can have only 00 of bit 5,6 . Hence such strings = 3

Total = 7
2
2
why so many upvotes on this answer!! you cant do this in exam...its lengthy
0
0
@Adarsh Pandey It won’t take time, some combinations will directly show that you can’t have enough inputs to reach final state and hence can be eliminated.
1
1
12 votes
12 votes

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)

4 votes
4 votes
option C

the strings are

1>1001001

2>1001011

3>1001101

4>1001111

5>1101001

6>1011001

7>1111001
Answer:

Related questions