Finite State Machine
A Finite State Machine (FSM) is a computational model used to design and analyze the behavior of systems. FSMs are characterized by a finite number of states, transitions between those states, and actions that result from those transitions.
1 Overview[편집 | 원본 편집]
A finite state machine consists of:
- A finite set of states.
- A finite set of inputs.
- A transition function that determines the next state for a given state and input.
- An initial state.
- (Optionally) a set of final or accepting states.
FSMs are widely used in computer science, engineering, linguistics, and other fields for modeling sequential logic and systems.
2 Types of Finite State Machines[편집 | 원본 편집]
Finite state machines can be classified into two main types:
- Deterministic Finite Automaton (DFA): For every state and input, there is exactly one transition to a next state.
- Non-Deterministic Finite Automaton (NFA): For some states and inputs, there can be multiple possible next states or transitions.
Both DFAs and NFAs are equivalent in expressive power but differ in their implementation and complexity.
3 Components[편집 | 원본 편집]
The main components of an FSM are:
- States: Represent distinct configurations or conditions of the system.
- Transitions: Define how the system moves from one state to another based on inputs.
- Inputs: External stimuli or events that trigger transitions.
- Outputs (Optional): Actions or signals produced as a result of state transitions.
4 Formal Definition[편집 | 원본 편집]
An FSM can be represented as a 5-tuple:
- Q: A finite set of states.
- Σ: A finite set of input symbols (alphabet).
- δ: The transition function (δ: Q × Σ → Q).
- q₀: The initial state (q₀ ∈ Q).
- F: The set of final or accepting states (F ⊆ Q).
5 Examples[편집 | 원본 편집]
5.1 Turnstile[편집 | 원본 편집]
A turnstile can be modeled as an FSM with two states:
- Locked: The turnstile is locked and requires a coin to unlock.
- Unlocked: The turnstile is unlocked and allows a person to pass.
| State | Input | Next State | Output |
|---|---|---|---|
| Locked | Insert Coin | Unlocked | Unlocks |
| Locked | Push | Locked | None |
| Unlocked | Push | Locked | Locks |
| Unlocked | Insert Coin | Unlocked | None |
5.2 Vending Machine[편집 | 원본 편집]
A vending machine is another example of an FSM. It processes coins and dispenses items when the correct amount is inserted.
6 Applications[편집 | 원본 편집]
Finite state machines are used in various domains, including:
- Designing digital circuits.
- Parsing and lexical analysis in compilers.
- Network protocols.
- Control systems and embedded systems.
- Game development for modeling NPC behavior.
7 Advantages[편집 | 원본 편집]
- Simple to design and understand.
- Easy to implement in hardware or software.
- Provides a clear visualization of system behavior.
8 Limitations[편집 | 원본 편집]
- Not suitable for modeling systems with infinite states.
- Can become complex and unwieldy for large systems.
