Please provide step by step solution thank you in advance

1. (20 points) Use induction over the size of strings to prove that the fol- lowing NFA over the alphabet ta, b q1 92 93 a b recognizes the regular language Y ab (that is, it accepts all w EY that end with at Hint: use the following statement as induction hypothesis (1) For each string w E Y a (i.e., strings that end with an a) all existing computation paths terminate either in state q1 or in state q2 (note that we consider only those computation paths that do not "die" in the middle of the computation) (2) For each string w EY ab all existing computation paths terminate either in state g1 Or in state ga. (3) For every other string (which is neither in 2 a nor in 2 ab, i.e., it belongs to Y*bb U b UE), all existing computation paths terminate in state q1 Note that since state q3 is the only accept state, this statement implies that the language of the above NFA is y ab (see item (2)). Therefore by proving this statement we also prove that ab is the language of the above automaton. In the base case you need to show that the statement holds for strings of size 0 and 1. As for the induction step, you need to show that the above induction hypothesis holds for all strings of fixed size n 2, assuming that it holds for all strings of size smaller than n For example, for each string w E a you need to show that there exists a computation path that terminates in q1 and there exists another comput tation path that terminates in q2. To do that you can consider the prefix of w of size n 1, for which the induction hypothesis holds