Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Definition Non Deterministic Finite Automata

A non-deterministic finite automaton (NDFA/NFA) is a 5-tuple (Q, Σ, δ, q0, F) 

where, 

  • Q = is a finite set of states. 
  • Σ = is a finite set of input symbols. 
  • δ = is a transition function mapping from Q × Σ to 2Q
  • q0 = is the initial state, q0 ∈ Q. 
  • F = is a set of final states, F ⊆ Q.
Reference: Introduction to the Theory of Computation” by Michael Sipser

Example of NFA,

Consider the NFA that accepts all string ending with 01.

Transition diagram
Transition table

In this NFA, 

M = {Q, Σ, δ, q0, F} 

where, 

  • Q = {q0, q1, q2}. 
  • Σ = {0, 1}. 
  • δ = As shown above. 
  • q0 = Initial state. 
  • F = {q2}

Reference:

  • Introduction to the Theory of Computation” by Michael Sipser.
Categories TOC