ISRO CSE 2014 | Question: 79

Question

Consider the following Deterministic Finite Automaton $M$.

Let $S$ denote the set of eight length bit strings whose second, third, sixth and seventh bits are 1. The number of strings in $S$ that are accepted by $M$ is

• A. 0
• B. 1
• C. 2
• D. 3

Comments

 

L(M)= Set of binary strings in which we have the first consecutive run of odd number of 0′𝑠  immediately followed by a run of odd number of 1′𝑠  followed by a string containing 01.

 odd number of 1's - that doesn't mean we can't have zero's in between - 1101 is also possible. 

Therefore the string 000-11-0101 can be viewed as 000-1101-01.

---

@Shaik Masthan, "run" in a string is defined as follows:

A run in a string is a substring of length at least two, as long as possible, and consisting entirely of the same symbol. For instance, the string abbbaab contains a run of b’s of length three and a run of a’s of length two.

So, as per above language description, 000-11-0101 is Not accepted. 

---

Here, we have some fixed positions (2nd, 3rd, 6th, and 7th) that must be 1. These occupy 4 positions in the 8-bit string. For the remaining 4 positions (1st, 4th, 5th, and 8th), the bits can be either 0 or 1. However, according to the given DFA, we can only start with 0. To reach the 3rd state, we must take one more step with 1 after fixing the starting 0.

For the 4th position, we can only take 1 and not 0. Similarly, the 5th position must be fixed as 0 due to the transitions in the DFA. Now, with two 1's fixed for the 6th and 7th positions, we have completed 7 positions of the string. These are all fixed, meaning the string can only follow this specific structure up to this point.

Finally, for the 8th bit, since we have already reached the last state of the DFA, taking either 0 or 1 in the self-loop always leads to the final state. Thus, there are 2 ways to complete the string.

In conclusion, there are exactly 2 valid strings accepted by the DFA. 

Valid strings are 01110110 and 01110111 only.

Answer 1

There are only Two cases a) and b) in which we get $2^{nd},3^{rd},6^{th},\text{and},\;7^{th}$ bits as $1$

1.

2. 

In case 1) we are not reaching at final state with $8$ bits

From Case 2)

The number of $8$ bit strings in S that are accepted by M =2

1. 01110111

2.01110110

Hence,(c)2 is the correct choice.

Comments

so 01110001 will also be accepted ....????

please reply......

---

You need to compulsorily have 6^th 7^th places as 1 so you can’t go towards 0.

---

There are only Two cases a) and b) in which we get $2^{nd},3^{rd},6^{th},\text{and},\;7^{th}$ bits as $1$

This is Not Correct. There are Many More ways in which we get $2^{nd},3^{rd},6^{th},\text{and},\;7^{th}$ bits as $1$ which are Not depicted in the two pictures. 

Detailed Video Solution: https://youtu.be/IAEX6O7jIis

Answer 2

Just looking at the finite Automata, there will be two string:

01100111

01100110

Answer 3

* 1 1 *  * 1 1 *  = 8 possibilites

out of 8 possibilites only below 2 strings will be accepted by given DFA.

01110111

01110110