1) Give Reason ( Algorithms for Finite Automata and whether polynomial or exponential, if not given in question, and why ? )

a) There is an exponential algorithm which, given a nondeterministic finite automaton, constructs an equivalent deterministic finite automaton. ? WHY ?

b) There is an exponential algorithm which, given a nondeterministic finite automaton, constructs an equivalent regular expression. WHY ?

(d) There is a polynomial algorithm which, given a deterministic finite automaton, constructs an equivalent deterministic finite automaton with the smallest possible number of states. WHY