DFA/NFA

DFA (Deterministic Finite Automata)

• every state must have a unique output for a specific input
• must have  one initial and at least one final state
•  transition function Q X ∑ →Q

NFA (Non-deterministic Finite Automata)

• a state may not require a unique output for a specific input
• its subsets  are in a power set
• transition function Q X (∑ U {∈})→2^Q

Both of these machines has 5 tuples
q₀ : initial state
Q: finite set of state
F: final state
𝛿: transition function
∑: set of alphabets