Vtgyjfy

I'm asked these two questions:

a) Is it true that for any Non-deterministic Finite Automata $M=(Q,Sigma, delta, q_0, F)$, the complement of $L(M)$ is equal to the set ${w in Sigma^* : delta^*(q_0, w) cap F = emptyset }$. If so, prove it, if not give a counterexample.

b) Is it true that for any Non-deterministic Finite Automata $M=(Q,Sigma, delta, q_0, F)$, the complement of $L(M)$ is equal to the set ${w in Sigma^* : delta^*(q_0, w) cap (Q-F) ne emptyset }$. If so, prove it, if not give a counterexample.

So the first thing I did was to make a concrete example where $M=(Q={q_0, q_1, q_2 }, Sigma ={1,0}, delta, q_0, F={q_2})$ NFA is accepted by the following regular expression: 10.

So, to take an example for part a):

1. $delta^* (q_0,10) = {q_2} cap {q_2} = {q_2}$


2. $delta^* (q_0,1) = {q_1} cap {q_2} = emptyset$

This is under the assumption that $F={q_2}$

And another example for part b):

1. $delta^* (q_0,10) = {q_2} cap {q_0,q_1} = emptyset$


2. $delta^* (q_0,1) = {q_1} cap {q_0,q_1} = {q_1}$

This is under the assumption that $overline F= Q-F = {q_0,q_1}$ since all the accepting states in the NFA become non-accepting, and all non-accepting become final states.

All this to say is that from the data I found with the two examples above, I cannot conclude anything and don't know how else to prove these two statements. Though what I'm leaning towards is that part a) is false because the first example is a counterexample $delta^* (q_0,10) = {q_2} cap {q_2} = {q_2}$, which is of course not a null set. However, this can also be said for part b) since $delta^* (q_0,10) = {q_2} cap {q_0,q_1} = emptyset$ does in fact give an empty set. So for part b), it would have been true if the statement in question to be proven was ${w in Sigma^* : delta^*(q_0, w) cap (Q-F) = emptyset }$. No?

Any hints or suggestions would be appreciated at this point because I'm quite confused.

Let me clarify things: $delta^*(q_0,w)$ represent the set of all states that can be reached by reading $w$ in the automaton.

So rephrasing the statements:

a) ask whether, $w$ is in the complement of $L(M)$ if and only if non of the states that can be reached by reading $w$ are accepting.

b) ask whether, $w$ is in the complement of $L(M)$ if and only if there exists a state that can be reached by reading $w$ and which is not accepting.

So your first example is not a counter example! In fact a) is true. It can be shown by showing the two inclusions.

For b), it is false. To see it you have to use the power of the non-determinism. Use a automaton that have an accepting run and an other run that is not accepting for the same word and see if the property hold.

I hope it clarify things for you.