Formal Definition of Finite Automata

Discrete Mathematics/Finite state automata

Formally, a Deterministc Finite Automaton is a 5-tuple D = (Q,Σ,δ,s,F) where:
Q is the set of all states.
Σ is the alphabet being considered.
δ is the set of transitions, including exactly one transition per element of the alphabet per state.
s is the single starting state.
F is the set of all accepting states.
Similarly, the formal definition of a Nondeterministic Finite Automaton is a 5-tuple N = (Q,Σ,δ,s,F) where:
Q is the set of all states.
Σ is the alphabet being considered.
δ is the set of transitions, with epsilon transitions and any number of transitions for any particular input on every state.
s is the single starting state.
F is the set of all accepting states.
Note that for both a NFA and a DFA, s is not a set of states. Rather, it is a single state, as neither can begin at more than one state. However, a NFA can achieve similar function by adding a new starting state and epsilon-transitioning to all desired starting states.
The difference between a DFA and an NFA being the delta-transitions are allowed to contain epsilon-jumps(transitions on no input), unions of transitions on the same input, and no transition for any elements in the alphabet.
For any NFA N, there exists a DFA D such that L(N) = L(D)


 A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q₀, F), consisting of

• a finite set of states (Q)
• a finite set of input symbols called the alphabet (Σ)
• a transition function (δ : Q × Σ → Q)
• a start state (q₀ ∈ Q)
• a set of accept states (F ⊆ Q)

Let w = a₁a₂ ... a_n be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r₀,r₁, ..., r_n, exists in Q with the following conditions:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

In words, the first condition says that the machine starts in the start state q₀. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).
A deterministic finite automaton without accept states and without a starting state is known as a transition system or semiautomaton.