Finite state machines are considered memoryless because they do not have external memory or variables to store information about previous inputs beyond their current state. All information about the past is encoded entirely in the current state of the machine. This means an FSM’s behaviour is solely determined by its current state and the input symbol being read, not by the full history of inputs. Despite this, FSMs can recognise patterns by designing states that reflect all necessary information about previous inputs relevant to the task. For instance, to recognise a binary string that ends with '01', an FSM only needs to remember the last two input symbols, which it does by transitioning through a series of states representing different symbol sequences. By carefully structuring states and transitions, FSMs simulate memory through state representation, allowing them to process and evaluate patterns without actual memory storage or counters.

A finite state machine can only have one start state by definition, as it must begin in a single, well-defined condition before processing any input. Multiple start states would create ambiguity in determining the initial configuration of the machine. However, it is valid for an FSM to have no accepting states. In such a case, no input string would ever be accepted, regardless of its content. This may seem pointless, but it can be useful in theoretical discussions or to model situations where no acceptable input is possible. Conversely, it is also valid for all states to be accepting, meaning that every string from the input alphabet would be accepted no matter what path the FSM takes. The configuration of accepting states is entirely dependent on the design purpose of the FSM. Whether none, one, or all states are accepting, the FSM must follow a strict structure: one start state and a complete transition function for every symbol in the input alphabet.

In a deterministic finite state machine (DFA), every state must have exactly one transition defined for each symbol in the input alphabet. This ensures that for any given input symbol, the machine always knows which state to move to. If a transition is missing, the FSM is incomplete and cannot process certain input strings, making it invalid under the deterministic model. To address this, FSMs include a special non-accepting state, often called a trap state or dead state. Any unexpected or undefined transition leads the machine into this trap state, which loops back to itself for all input symbols. Once the FSM enters the trap state, it cannot leave and will always reject the input. This guarantees the transition function is total and allows the FSM to handle all possible strings over the input alphabet gracefully. Including such a state is considered good practice when designing robust deterministic FSMs.

The number of states in a finite state machine directly impacts both its clarity and efficiency. More states can improve clarity by representing specific conditions more explicitly, making the FSM easier to understand, especially for complex input patterns. However, increasing the number of states also increases the visual and structural complexity of the FSM, making it harder to maintain or trace. On the other hand, minimising the number of states can make the machine more efficient in terms of storage and processing time, particularly in software or hardware implementations. However, excessive minimisation can make the FSM difficult to interpret or debug. Striking a balance is key: an efficient FSM has the minimum number of states needed to fulfil its purpose without becoming overly complex. In practice, designers often optimise FSMs using state minimisation techniques, but for A-Level purposes, the focus is on designing clear, correct, and readable FSMs suited to simple tasks.

Yes, multiple FSMs can accept the same language — meaning they accept exactly the same set of strings — even if they have different structures. This is a common situation in theoretical computer science and is related to the idea of FSM equivalence. Two FSMs are considered equivalent if they accept the same language, regardless of how many states they have or how their transitions are arranged. One FSM might use fewer states by combining conditions into single states, while another might use more states for clarity by separating those conditions. This reflects the fact that FSM design can be flexible and depends on the designer’s choices regarding clarity, simplicity, or efficiency. Even though two FSMs behave identically in terms of which strings they accept or reject, their internal logic may be implemented in different ways. Determining whether two FSMs are equivalent can involve checking that, for all input strings, both machines always accept or reject together.