# Proof of existence of prefix in NFA

Let $$A= (Q,Σ,δ,s,F)$$ be a NFA. Prove the following statement:

$∀q ∈ Q: (∃ w_2 ∈ Σ^* :δ (q, w_2) ∩ F \ne ∅ ⇒ ∃w_1 ∈ Σ^*:w_1w_2 ∈ L(A))$

I figured out that it means that if all the states have a path to the final state, that the word describing their path is a suffix of a word that is accepted from the NEA.

The thing is: How can I be sure that the NEA accepts all words with that suffix if it doesn't start from the s state.

• Are you sure you copied the statement correctly? We cannot help you otherwise. Nov 17 '17 at 20:52
• It's absolutely correct. Nov 17 '17 at 21:53
• What's a NEA? Did you mean NFA?
– D.W.
Nov 17 '17 at 22:30
• Yes. I meant NFA. Nov 18 '17 at 9:59

The statement is false. Consider the NFA on the alphabet $\{a\}$ having two states: an initial state $q_0$, and the unique final state $q_f$. The transition function is given by $\delta(q_0,a) = \{q_0\}$ and $\delta(q_f,a) = \{q_f\}$. For every word $w_2$ it is the case that $\delta(q_f,w_2) \cap F = \emptyset$, yet $w_1 w_2 \notin L(A)$ for all $w_1$.
• You're confusing the order of quantifiers. The statement claims that for all states $q$, something is true. That something is that there exists a word $w_2$ so that the following holds: if $\delta(q,w_2) \cap F \neq \emptyset$ then there exists a word $w_1$ such that $w_1w_2 \in L(A)$. Nov 17 '17 at 22:02
• I show that this statement is false for my NFA, by showing that it is false for the state $q_f$. Nov 17 '17 at 22:02