Problem Detail: I am trying to make a non-deterministic NFA that does not contain a string “101”. How do I make my NFA so that it does not have this string? My attempt: 
Asked By : Kadana Kanz
Answered By : Raphael
I’ll give you a recipe for constructing automata for $Sigma^* setminus F$ for any regular $F subseteq Sigma^*$.
- Construct a (complete) DFA $A_F$ for $F$.
- Construct the complement automaton $overline{A_F}$.
- Optional: minimise.
The first step is particularly easy (if maybe time consuming) for finite $F$. The second one is standard (flip accepting and non-accepting states) and should be covered by any textbook on this subject. Of course, step 1 may blow up the size of the automaton (going from an easy-to-design NFA to DFA); this can in particular be the case for finite sets. In your particular case, though, you never get more than five states.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41282 Ask a Question Download Related Notes/Documents
