HQ5 [2 pages] Design an efficient algorithm to convert an NFA N=<Q,S,d,q0,F> that has epsilon transitions to another NFA M that does not have any epsilon transitions. The number of additional states should be as little as possible (can you use no additional states?). The standard approach of first converting N to a DFA can exponentially blowup the number of states. In fact, when converting an arbitrary NFA (that may have epsilon transitions) to a DFA, it is advised to first apply the above method to create a smaller NFA with no epsilon transition and then apply the subset method. 
(a) Design an algorithm (in pesudocode, avoid actual code, and add comments/explanation to enhance clarity) that takes N as input and outputs M with no epsilon transition. 
(b) Analyse the complexity of your algorithm – I am not looking for a very tight analysis of your algorithm.(c) Prove that your algorithm is correct (first, state formally in level-1 what it is that you want to prove, and then prove those in level-2).