Q91: Grammar of the NFA.

This question is in continuation with Q86 and Q89

Question 91: What is the grammar of the above NFA?

1. a*b*(abb)*
2. (a|b)*abb
3. (ab)*abb
4. Both B and C

Solution: The first block is either a or b as many times as possible, then it must be followed by abb before reaching final state. So, it accepts all of the strings ending with abb. The correct answer is option 2.

Q72: DFA of complement of regular language

Question 72: If M is a DFA accepting a language P. How can the DFA of complement of the regular language P be constructed?

1. The complement of a regular language is not regular, hence DFA of the complement can’t be constructed.
2. The complement of a regular language is regular, but however, its DFA can’t be constructed.
3. The DFA of the complementary language can be constructed by reversing the transitions of DFA.
4. The DFA of the complementary language can be constructed by exchanging the final and non-final states.

Solution: All of the strings which were accepted by M should not be accepted by new DFA, hence the final states become non-final. Similarly, all of the strings which were not accepted by M should be accepted by new DFA, hence non-final states become final states. Hence, the correct answer is option 4.

Q41: Yet another DFA

Question #41: What is the language of the DFA below?

 

Options:

1. L = {w | w has an even number of b’s and each a is followed by at least one b}
2. L = {w | w has an even number of a’s and each b is followed by at least one a}
3. L = {w | w has an even number of b’s and each b is followed by at least one a}
4. L = {w | w has an even number of a’s and each a is followed by at least one b}

Solution:

1C and 2C are dead states because once we go them, we can never reach final state. After every transaction of a, we have at least one transition of b, hence each a is followed by at least one b. Also, we have even number of a’s to reach to final state. Hence, the correct answer is option 4.

Q10: Language of DFA

Question #10: What is the language of the DFA below?

 

Options:

1. All string having even number of 0’s
2. (1*01*01*)*
3. All strings which end with 1 + empty string
4. Both options 1 and 2

Solution: The above DFA accepts strings of  even number of 0’s, making option 1 the only correct answer. Note that option 2 is incorrect because it doesn’t include the string (1)* which is included in the DFA.