6.2.3 FSM States

TL;DR

Finite State Machines (FSMs) can have at most 2^K states based on K state bits, and the number of states in a FSM series is M*N. It is possible to discover the behavior of an FSM with a known upper bound on the number of states, and different FSMs with different state counts can be externally indistinguishable and interchangeable.

Transcript

Let’s think a bit more about the FSM abstraction. If we see an FSM that uses K state bits, what can we say about the number of states in its state transition diagram? Well, we know the FSM can have at most 2^K states, since that’s the number of unique combinations of K bits. Suppose we connect two FSMs in series, with the outputs of the first FSM s... Read More

Key Insights

• #️⃣ The maximum number of states in an FSM with K state bits is 2^K, based on the number of unique combinations.
• 🇲🇰 Connecting FSMs in series results in a larger system with an upper bound of M*N states, where M and N are the number of states in the individual FSMs.
• #️⃣ Discovering the behavior of an FSM with a known upper bound on the number of states is possible by testing all possible K-step input sequences from the initial state.
• 🔄 FSMs with different state counts can be equivalent if their input-output sequences are identical.

Questions & Answers

Q: Can you explain the relationship between the number of state bits and the maximum number of states in an FSM?

The number of state bits in an FSM, denoted by K, determines the maximum number of states which is 2^K. This is because K bits can form 2^K unique combinations, each representing a different state.

Q: What is the upper bound on the number of states in a system formed by connecting two FSMs in series?

When two FSMs are connected in series, the larger system can have at most M*N states, where M is the number of states in the first FSM and N is the number of states in the second FSM.

Q: How can the behavior of an FSM with a known upper bound on the number of states be discovered?

By testing all possible K-step input sequences, where K is the upper bound on the number of states, starting from the initial state, every state in the FSM can be visited and its behavior can be determined.

Q: What does it mean for two FSMs to be equivalent?

Two FSMs are considered equivalent if every input sequence produces identical output sequences from both FSMs. They can be externally indistinguishable and interchangeable in practical applications.

Summary & Key Takeaways

• FSMs with K state bits can have a maximum of 2^K states due to the number of unique combinations.

• Connecting two FSMs in series results in a larger system with an upper bound of M*N states.

• The state transition diagram of an FSM with two inputs and one output can be discovered by testing various input sequences.