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.

Any leads?

  • $\begingroup$ Are you sure you copied the statement correctly? We cannot help you otherwise. $\endgroup$ Nov 17 '17 at 20:52
  • $\begingroup$ It's absolutely correct. $\endgroup$
    – Billy Joel
    Nov 17 '17 at 21:53
  • 1
    $\begingroup$ What's a NEA? Did you mean NFA? $\endgroup$
    – D.W.
    Nov 17 '17 at 22:30
  • $\begingroup$ Yes. I meant NFA. $\endgroup$
    – Billy Joel
    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$.

  • $\begingroup$ It has to be true for all words starting from q_0 too. In this case there isn't a word w_2 for q_0 with which we end up in a final state. $\endgroup$
    – Billy Joel
    Nov 17 '17 at 21:52
  • $\begingroup$ 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)$. $\endgroup$ Nov 17 '17 at 22:02
  • $\begingroup$ I show that this statement is false for my NFA, by showing that it is false for the state $q_f$. $\endgroup$ Nov 17 '17 at 22:02
  • $\begingroup$ This leads me to believe that you either copies the statement wrong, or forgot to include the assumption that all states are reachable from the initial state. $\endgroup$ Nov 17 '17 at 22:03
  • $\begingroup$ I see what I've missed. I didn't get the quantifiers wrong, I just misinterpreted the implication. I assumed that it should be true for all states that they can reach the final state. The thing is that it must hold true only for states that DO end up in final states. Anyway thanks for the quick response as always :) $\endgroup$
    – Billy Joel
    Nov 17 '17 at 22:10

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.