Question

A state \({\bf{s'}}\) in a finite-state machine is said to be reachable from state \({\bf{s}}\) if there is an input string \({\bf{x}}\) such that \(f(s,x){\bf{ = s'}}\). A state \({\bf{s}}\) is called transient if there is no nonempty input string \({\bf{x}}\) with \({\bf{f(s,x) = s}}\). A state \({\bf{s}}\) is called a sink if \({\bf{f(s,x) = s}}\) for all input strings \({\bf{x}}\). Answer these questions about the finite-state machine with the state diagram illustrated here.

\(a)\)Which states are reachable from \({s_0}\)\(?\)

\(b)\)Which states are reachable from \({s_2}\)\(?\)

\(c)\)Which states are transient\(?\)

\(d)\)Which states are sinks\(?\)

Short answer

\((a)\)The reachable states are \({s_0},{s_1},{s_2},{s_4},{s_5},{s_6}\).

\((b)\)The reachable states are \({s_2},{s_5}\).

\((c)\)The reachable states are \({s_0},{s_1},{s_3},{s_6}\).

\((d)\) The reachable states are \({s_4},{s_5}\).

Step-by-step solution

Definition

A state is reachable from state \({\bf{s}}\) if there exists an input string \({\bf{x}}\) such that \(f(s,x){\bf{ = s'}}\).

A state is transient if there is no nonempty input string \({\bf{x}}\) such that \({\bf{f(s,x) = s}}\).

A state \({\bf{s}}\) is a sink if \({\bf{f(s,x) = s}}\) for all input strings \({\bf{x}}\).

Finding the reachable states 

(a)

If use the empty string when starting from the state \({s_0}\), then it ends up at the state \({s_0}\) and thus \({s_0}\) is reachable from \({s_0}\).

\({s_0}\)is reachable.

If there is an arrow from \({s_0}\) to \(t\) in the given state diagram, then the state \(t\) is reachable from \({s_0}\).

\({s_1}\)is reachable.

\({s_6}\)is reachable.

If there is an arrow from \(t\) to \(u\) in the given state diagram with \(t\) reachable from \({s_0}\), then the state \(u\) is also reachable from \({s_0}\).

\({s_2}\)is reachable.

\({s_4}\)is reachable.

\({s_5}\)is reachable.

Note that all states are reachable from \({s_0}\) except the state \({s_3}\).

Therefore, the reachable states are \({s_0},{s_1},{s_2},{s_4},{s_5},{s_6}\).

Finding the reachable states

(b)

If use the empty string when starting from the state \({s_2}\), then it ends up at the state \({s_2}\) and thus \({s_2}\) is reachable from \({s_2}\).

\({s_2}\)is reachable.

If there is an arrow from \({s_2}\) to \(t\) in the given state diagram, then the state \(t\) is reachable from \({s_2}\).

\({s_5}\)is reachable.

If there is an arrow from \(t\) to \(u\) in the given state diagram with \(t\) reachable from \({s_2}\), then the state \(u\) is also reachable from \({s_2}\). However, there are no arrows from \({s_5}\) to another state and thus it has found all reachable states.

Note that \({s_2}\) and \({s_5}\) are reachable from state \({s_2}\).

Therefore, the reachable states are \({s_2},{s_5}\).

Finding the reachable states

(c)

A state \({\bf{s}}\) will be transient if there are no loops at the state \({\bf{s}}\) nor a loop from the state \({\bf{s}}\) to the state \({\bf{s}}\).

Then note that \({s_2}\), \({s_4}\) and \({s_5}\) are not transient as there are loops at these states.

\({s_0}\), \({s_1}\), \({s_3}\), \({s_6}\) are then transient, because the only incoming arrows to the state originate from another transient state.

Therefore, the reachable states are \({s_0},{s_1},{s_3},{s_6}\).

Finding the reachable states

(d)

A state \({\bf{s}}\) is a sink if there is a loop with input \(0\) and input \(1\) at the state \({\bf{s}}\).

\({s_2}\), \({s_4}\), \({s_5}\) are the only states with loops.

However, \({s_2}\) does not have a loop with input \(1\) and thus \({s_2}\) is not a sink.

\({s_4}\)and \({s_5}\) are sinks as they have loops for both input values.

Therefore, the reachable states are \({s_4},{s_5}\).