DO NOT COPY OTHER ANSWERS OFF CHEGG OR I WILL DOWNVOTE!

1. (15 points) A septa NFA is a NFA that accepts a word w if there exist computation paths for w such that one-seventh or more of the ending states are accepting. (That is, let Sy be the set of states that the septa NFA could end up in after processing an input w. Let F be the set of accepting states of the septa NFA. Then, if Sv 70 and ISOF SU >, then the septa NFA should accept w. Otherwise, it should reject w.) Show that DFAs are equivalent to septa NFAs. In other words, (a) Show that for every DFA M there exists a septa NFA N that accepts the same language. (b) Show that for every septa NFA N there exists a DFA M that accepts the same language. Note that one direction will be harder than the other. For each part, provide a complete and rigorous construction of the septa NFA or DFA as appropriate and provide an explanation as to why your construction works