HQ4. [Page limit 2 pages] You are given an NFA N=. Construct another NFA M= where E is defined as the set of those states that have some path (using 0 or more transitions) to some final state.
(a) Give a recursive definition of E and use that to design an algorithm to construct E just like we did for e-closure.
(b) Give a simple interpretation of the strings in L(M), i.e., construct a language K that “intuitively” represents the strings accepted by M. Hint: Feel free to use standard string operations/operators.
(c) Give a formal proof that M indeed accepts K using d'. You may first want to present a set theoretic characterisation of E (e.g., E = { q in Q : … }). Hint: Avoid the temptation to use graph-theoretical notations like edge, path, etc.