(a) Give an NFA with four states that recognizes L₁ = {w {0, 1} | w contains 110 as a substring }. (You can actually give a DFA with four states that recognizes this language. Your NFA should be simpler than this DFA in the sense that it does not have any cycles except for self-loops.)

(b) Give an NFA with two states that recognizes the language L₂ = 0 12 0 2 .