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.