I am taking a theory of computation course, and I am stuck in one of my assignment question. Any help or guidance is much appreciated. Here is the problem.
Let $M$ be a DFA that accepts a language $A$ over the alphabet $\{0,1\}$. Design a NFA (using $M$) that accepts the following language: $A \setminus \epsilon$.
My thinking: NFA is considered to be a NFA if there is the use of epsilon, or different states we can go to with the same input symbol. However, not knowing which DFA we re dealing with, I have a hard time how I can use that M to design the NFA. Thank you very much.
First of all, if the initial state $i$ of your DFA is not a final state, then the empty word is not in $A$ and there is nothing to do since $A - \varepsilon = A$.
If now $i$ is a final state, make it nonfinal. Then create a new final state $i'$ and replace each transition of the form $q \xrightarrow{c} i$ (where $c \in \{0,1\}$) by $q \xrightarrow{c} i'$. Finally add a transition $i' \xrightarrow{\varepsilon} i$. The resulting NFA will accept $A - \varepsilon$.