3

If a finite state machine is formally defined with a set of states $\{q_0, q_1, q_2\}$, where $q_0$ is the start state, is it a valid machine if there is no path from $q_0$ to $q_1$ and no path from $q_2$ to $q_1$? In other words, there is no way to reach $q_1$ at all, but it is still considered part of the machine.

Furthermore, what if $q_1$ is the only accept state in the machine? Is it still a valid finite state machine?

Hagen von Eitzen
  • 374,180
Solomon
  • 33
  • 1
    Yes. However, you can simplify this machine without changing it's behavior. Call a state accessible if there is a path from an initial state to it. Call the state co-accessible if there is a path from it to a final state. If you build a new finite state machine where you only keep states that are both accessible and co-accessible (and transitions between them), it will recognize the same langage. – xavierm02 Sep 15 '16 at 17:05
  • Yes. The definition of an FSM allows unreachable states and allows having just one accepting state. – avs Sep 15 '16 at 17:06

1 Answers1

1

There is no theoretical reason to forbid this. Then again, you may want to make the definition in such a way that this condition is enforced - but then you always have to prove for each construction (e.g., combining "subroutines" into a larger machine) that the condition is not suddenly violated. Thus form a theoretical standpoint, it is simpler to allow such redundant states.

If $q_1$ is the only accept states, the machine is equivalent to a machine without any accept state; which is not problematic, it just says that the machine accepts precisely the empty language.

Maybe you write down a machine that reaches an accept state only upon input of an even number $>2$ that cannot be written as sum of two primes. Would you agree that such a machine is a machine? Or would you require me to prove that the Goldbach conjecture is false before you considere this a machine?

Hagen von Eitzen
  • 374,180