$1.$ Give DFA's accepting the following languages over the alphabet f$0$; $1$g:

$($a$)(15$ marks$)$ The set of all strings with $101$ as a substring. Prove the correctness of your DFA using state invariants.

$($b$)(15$ marks$)$ The set of all strings with the $11$ as a substring. Prove that your DFA has minimal number of states using techniques shown in class.

$($c$)(5$ marks$)$ The set of strings ending in $110.($no proofs required here$)$