DFA - Deterministic Finite Automata

DFA - Deterministic Finite Automata

DFA is a language checker and a pattern checker which check are we following correct sequence or not . If we follow we are passed else not passed.

Automata

Automata refers to a machine that represents a language and determines whether a given input belongs to that language. It helps decide whether a sequence of symbols follows a set of predefined rules.

DFA Breakdown

• Q → Set of all finite states.
• Σ (Sigma) → Input alphabet (set of allowed symbols).
• δ (Delta) → Transition function, which determines movement between states.
• q₀ → Start state (initial state).
• F → Set of final (accepting) states. Multiple final states are possible.
• F ⊆ Q → Final states are a subset of total states.

Example: DFA for Strings Starting with 'a'

The DFA accepts all strings where the first letter is 'a', such as {a, aa, aaa, ab, aabc, ...}, an infinite language.

State Transitions

1. q₀ (Start State):
   • If the first letter is 'a', move to q₁ (Accepting State).
   • If the first letter is anything else (e.g., 'b'), move to q₂ (Rejecting State).
2. q₁ (Accepting State):
   • Any further input keeps the DFA in q₁ (remains accepted).
3. q₂ (Rejecting State):
   • Any further input keeps the DFA in q₂ (remains rejected).

State Diagram Representation:

q₀ -- a --> q₁ (Accepting State)  
q₀ -- b --> q₂ (Rejecting State)  
q₁ -- (a, b) --> q₁  
q₂ -- (a, b) --> q₂