0
$\begingroup$

enter image description here

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

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – G. Bach Feb 2 '16 at 16:25
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ this counterexample is correct ? automata that accept L :i.stack.imgur.com/kQPNP.png the complement of L: i.stack.imgur.com/lQArV.png $\endgroup$ – Med Choaib Assoualma Feb 5 '16 at 10:52
  • $\begingroup$ 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$. $\endgroup$ – Denis Pankratov Feb 6 '16 at 18:48

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.