Finite-state machine

Some machines follow a set plan.

A gate can be locked or unlocked. You put in a coin to unlock it. Then you push through to pass. After that, it locks again.

This is called a state machine. It can be a turnstile or a vending machine. It can even be a traffic light. These machines change what they do based on what happens. They use a list of states to work. This helps them know what to do next.

Imagine a gate at a subway station.

It can be in two states: locked or unlocked. If you push the gate while it is locked, nothing happens. But if you put in a coin, the state changes to unlocked. Once you push through, it changes back to locked. This is a finite-state machine.

A finite-state machine is a way to model how things work. It can only be in one state at a time. It changes states when it receives an input. This change is called a transition. These machines are used in many things. Vending machines, elevators, and traffic lights all use them.

There are different kinds of these machines. Some are called acceptors. They look at a sequence of symbols to see if it fits a rule. Others are called transducers. These machines produce an output based on the state or the input.

For example, an elevator door uses these ideas to open and close. These machines have a set amount of memory. This memory is limited by how many states they have.

A finite-state machine is a way to model how a system works. It is an abstract machine that can be in exactly one state at any time. A state is a description of what the system is doing while it waits for something to happen. When the machine receives an input, it can change from one state to another. This change is called a transition.

These machines are very important for understanding how different things function. They help us map out a set of rules for a machine to follow.

To understand how they work, imagine a simple turnstile at a subway station.

A turnstile has two possible states: Locked and Unlocked. If the machine is in the Locked state, pushing the arm does nothing. However, if you provide the input of a coin, the machine undergoes a transition to the Unlocked state. Once a person pushes through the gate, the machine moves back to the Locked state.

You can draw these movements using a state diagram. In these diagrams, circles represent the states and arrows show the transitions.

People use these models in many different areas of study. Scientists and experts study them in a field called automata theory. This field looks at how machines process information. You can find these ideas in electrical engineering and computer science. They are also used in biology, philosophy, and even video game programming.

These models help engineers design hardware and software that works correctly. They are also used to study how languages are formed.

There are different types of these machines based on what they do. Acceptors are machines that look at a sequence of symbols. They decide if the input is accepted or rejected based on a rule.

For example, an acceptor might check if a binary number has an even number of zeros. Transducers are another type that produce an output.

Some transducers are called Moore machines, where the output depends only on the state. Others are called Mealy machines, where the output depends on both the state and the input.

These machines are much simpler than some other models of computation. A famous model called a Turing machine is much more powerful. This is because a finite-state machine has limited memory. Its memory is restricted by the total number of states it has.

You can see these ideas in your daily life all the time. Vending machines, elevators, and traffic lights all follow a set sequence of actions. Even a combination lock uses these rules to check your numbers in the right order. They all rely on moving through states to finish a task.

A finite-state machine (FSM) is a mathematical model of computation. It is an abstract machine that exists in exactly one of a finite number of states at any given time. These states represent the current status of a system while it waits for an event. When the machine receives a specific input, it can undergo a transition. A transition is the process of changing from one state to another.

This model is fundamental to automata theory, which is the study of machines and their computational abilities. FSMs are essential for designing systems that must follow a predetermined sequence of actions based on external events.

To understand the mechanism, consider the inputs and transitions that define an FSM. An FSM is formally defined by a list of its states, its initial state, and the inputs that trigger each transition. For example, a turnstile can be modeled as a state machine with two states: Locked and Unlocked.

In the Locked state, the input of a coin triggers a transition to the Unlocked state. However, the input of a "push" while in the Locked state results in no change. Once the machine is Unlocked, a "push" input triggers a transition back to the Locked state.

This behavior can be mapped using a state-transition table or a state diagram. In a state diagram, nodes represent states and directed edges, or arrows, represent the transitions triggered by inputs.

There are two primary types of finite-state machines: deterministic and non-deterministic. In a deterministic finite-state machine (DFSM), each input leads to exactly one specific next state. This makes the behavior predictable and certain. In a non-deterministic finite-state machine (NFSM), an input might allow for multiple possible next states. Despite this difference, any non-deterministic machine can be converted into an equivalent deterministic one. This mathematical equivalence allows engineers to use non-deterministic models to simplify complex designs before implementing them as deterministic systems.

FSMs are categorized by their specific functions into four groups: acceptors, classifiers, transducers, and sequencers. Acceptors, also known as recognizers, produce a binary output to indicate if an input sequence is accepted or rejected.

An acceptor determines if a sequence of symbols belongs to a formal language, known as a regular language. For instance, a machine can be designed to accept only binary strings that contain an even number of zeros.

Classifiers are a more complex version of acceptors that produce n-ary output, where n is greater than two. Sequencers are a specific subclass that use a single-letter input alphabet to generate sequences.

Transducers are machines that produce outputs based on inputs and current states. They are used heavily in control applications and computational linguistics. There are two major models of transducers: Moore machines and Mealy machines. In a Moore machine, the output depends solely on the current state.

This is useful for simplifying behavior, such as an elevator door that signals "open" or "closed" based on its state. In a Mealy machine, the output depends on both the current state and the input received.

Mealy machines often require fewer states to perform the same task as a Moore machine.

Historically and theoretically, FSMs occupy a specific place in the hierarchy of computational power. An FSM has less computational power than a Turing machine. This limitation exists because an FSM's memory is strictly limited by its finite number of states. A Turing machine can perform tasks that an FSM cannot because it has much more flexible memory. However, an FSM is equivalent in power to a Turing machine that is restricted to only "read" operations and can only move its head in one direction, from left to right.

Today, the applications of finite-state machines are vast and diverse. They are used in electrical engineering to design digital hardware and in computer science for software engineering and network protocols. In linguistics, they help model how languages function.

You can see FSM logic in everyday devices like vending machines, elevators, and traffic lights. Even a combination lock is a physical manifestation of a state machine, as it requires a specific sequence of inputs to reach the final state. From video game programming to biology, these mathematical models help us organize and understand complex, reactive systems.