[Solved]: NFA not accepting a certain string

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

1. Construct a (complete) DFA $A_F$ for $F$.
2. Construct the complement automaton $\overline{A_F}$.
3. 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