If we have a language K, that word w=uv, accepts. $K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \ \text{is not divisible by 3}}\}$. Can we land strings like aaaa in final state? How does NFA decides to break up the string in this case, would it be u = aa, v = aa (w accepted) or u = aaa, v = a (w is not accepted). Or doesn't matter and we can land everything as long as right decomposition exists.

  • 1
    $\begingroup$ NFA is, as the name says, non-deterministic. There might be several paths for one input string. As long as the NFA is correct and the input string is an acceptable string, there exists a path to reach the final state. $\endgroup$
    – bigbang
    Commented May 9, 2021 at 10:01
  • 2
    $\begingroup$ I suggest looking up the definition of the language accepted by an NFA. The definition contains all the information you need. $\endgroup$ Commented May 9, 2021 at 19:12
  • $\begingroup$ I don't understand the definition of $K$. Do you require that $w$ has a prefix $u$ such that $|u|_a$ is not divisible by $3$? In this case, $K = \{a,b,c\}^*a\{a,b,c\}^*$ $\endgroup$
    – J.-E. Pin
    Commented May 10, 2021 at 8:48


Your Answer

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

Browse other questions tagged or ask your own question.