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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.