2
$\begingroup$

I am currently preparing for exam. While studying Finite Automata, i got confused. I know a DFA can have multiple accepting states, but can an NFA also have multiple accepting states?

$\endgroup$
6
$\begingroup$

Whenever one is in doubt about central notions, one must consult the definitions of them. You should do this yourself (I assume that you have a textbook at your disposal).

Below is Definition 1.37 from Introduction to the Theory of Computation by Michael Sipser:

A nondeterministic finite automaton is a 5-tuple $(Q,\Sigma,\Delta,q_0,F)$, where

  1. $Q$ is a finite set of states,
  2. $\Sigma$ is a finite alphabet,
  3. $\delta: Q \times \Sigma_{\epsilon} \rightarrow \mathcal{P}(Q)$ is the transition function,
  4. $q_0 \in Q$ is the start state, and
  5. $F \subseteq Q$ is the set of accept states.

Item 5 tells us that $F$ is just a set of states, which means that it can be the empty set, a singleton set or a set with several states as elements.

| 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.