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

Improve this question
$\endgroup$
1
  • 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
    Commented Feb 2, 2016 at 16:25

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ this counterexample is correct ? automata that accept L :i.sstatic.net/kQPNP.png the complement of L: i.sstatic.net/lQArV.png $\endgroup$
    – Med Choaib Assoualma
    Commented Feb 5, 2016 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
    Commented Feb 6, 2016 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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