3.3k views

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$
edited | 3.3k views
0

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
+4
The regular expression I got by Arden's theorem is (1+0)*000*1(1+0)*

How can we skip 0* which was in the middle?

+5
The language of above DFA is all strings over {0,1} that contain substring 001.

S =  1_ _1_ _1

Now use PnC.

Strings of the following forms will be accepted by M

1) 1001xx1       2)1xx1001              here x can be 0 or 1.

so no. of strings possible = 2*2*2=8 but 1001001 is counted 2 times so 8-1 =7.
+1

pls explain the regular expression for this dfa using state elimination method

0

Soumya29 Is this general for all the cases??

0
+1
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
0

The language of the DFA is not

contains substring "001"

It is actually

contains substring "00" followed by a "1"

The difference here is that the "1" can come any time after the "00". It is not necessary that it should immediately follow the "00". Just that there should be a "1" somewhere along the string (after the "00") for it to be accepted.

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.

+1
very nice solution.
0
Easy and best
+1
nice solution ... ] sometimes we can compromise our speed for accuracy..in exam hall i will prefer this no need to think a lot just mark and move it will not take more then 2min
0
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
option C

the strings are

1>1001001

2>1001011

3>1001101

4>1001111

5>1101001

6>1011001

7>1111001

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 :

Ans 7

Can be easily done via brute force method.

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

1