1
$\begingroup$

In two way non-deterministic finite state automata there is the concept of reject state.

Since an input is accepted if any one of the parallel branches in the Non Deterministic FSA reaches an accept state and the rest of the branches are then immaterial.

  1. On a given Input even if one of the branches reaches the 'reject' state and the other reaches the accept state (after processing the last input symbol) what do we do ?

  2. If one of the branch reaches the reject state before processing the complete input what do we do? Continue processing the other branches that might lead to accepting the input and terminate only the local branch? Or the input is rejected (similar to accept state)?

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

As you clearly state, an input is accepted, by definition, if one of the parallel branches accepts. This means that an input is accepted if and only if at least one of the parallel branches accepts. So if one brach accepts and another rejects, the input is accepted.

In non-deterministic automata, acceptance and rejection are not symmetric. An input is accepted iff there is some accepting computation path. An input is rejected iff all computation paths are rejecting.

| cite | improve this answer | |
$\endgroup$

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.