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.
==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.
==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.
==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.
==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).
==Examples==
===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.
{| class="wikitable"
!State!!Input!!Next State!!Output
|-
|Locked||Insert Coin||Unlocked||Unlocks
|-
|Locked||Push||Locked||None
|-
|Unlocked||Push||Locked||Locks
|-
|Unlocked||Insert Coin||Unlocked||None
|}
===Vending Machine===
A vending machine is another example of an FSM. It processes coins and dispenses items when the correct amount is inserted.
==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.
==Advantages==
*Simple to design and understand.
*Easy to implement in hardware or software.
*Provides a clear visualization of system behavior.
==Limitations==
*Not suitable for modeling systems with infinite states.
*Can become complex and unwieldy for large systems.
==See Also==
*[[Deterministic Finite Automaton]]
*[[Non-Deterministic Finite Automaton]]
*[[State Transition Diagram]]
*[[Turing Machine]]
[[Category:Theoretical Computer Science]]