To Do : Deterministic Finite State Machines - mbits-mirafra/digitalDesignCourse GitHub Wiki

Definition

A Deterministic Finite State Machine (DFSM) is a 5-tuple (Q, Σ, δ, q0, F), where:

Q is a finite set of states.
Σ is a finite alphabet of input symbols.
δ: Q × Σ → Q is a transition function that maps a state and an input symbol to a next state.
q0 ∈ Q is the initial state.
F ⊆ Q is a set of accepting/final states.

In a DFSM, for each input symbol, there is exactly one transition from each state to the next state. This means that the machine has a unique next state for every input symbol in every state.

State Diagram Representation

A DFSM consists of a finite set of states, a set of input symbols or alphabet, a transition condition that specifies the next state given the current state and input symbol, a start state, and a set of accept states or final states.

The input is processed one symbol at a time, and the DFSM moves from state to state based on the transition function until the end of the input is reached. If the final state is an accept state, then the input is accepted by the DFSM, otherwise it is rejected.

DFSMs can be represented with state diagrams, where the circles with the symbol inside represent the states, the arrows represent transitions and the symbols near the arrows represent transition conditions. The accept states are usually indicated by double circles.