# complement of a language-nfa

hi i know that the question 5 is true because by definition w ∈ L if and only if δ*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L"

but iam really confused about the question 6 our teacher told us that it's false but i think it's true because i don't see any difference between the 2 questions

i get this picture from peter linz book : An-Introduction-to-Formal-Languages-and-Automata

• We have pretty $\LaTeX$ here! The argument for 5 is correct, for 6 it doesn't work this way; can you rephrase the acceptance criterion for NFAs by using an intersection with $Q - F$? – G. Bach Feb 2 '16 at 16:25

Your teacher is right. $\delta^*(q_0, w) \cap (Q - F) \neq \emptyset$ does not necessarily imply that $\delta^*(q_0, w) \cap F = \emptyset$. Question 5 says that you don't terminate in any of the accept states, question 6 says that you terminate in some non accepting states, but NFA can still terminate in some accepting state.
• No, the NFA you gave does not work - it does not have nonaccepting states. To provide a counterexample, you need to give NFA $N$ and a string $x$ such that $x$ can end up in both accepting and nonaccepting states of $N$. – Denis Pankratov Feb 6 '16 at 18:48