Q143: Language of the following NFA

Question 143: What is the language of the NFA below?

1. (0|1)*11(0|1)* | (0|1)*101(0|1)*
2. All strings only having substring as 101
3. All strings only having substring as 11
4. (0|1)*111(0|1)* | (0|1)*101(0|1)*

Solution: The correct answer is option 1. At very first place, we can have any number of 0’s or 1’s, which must be followed by 1, 0 or epsilon, and another 1. Then again, we can have any number of 0’s or 1’s.

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.