Finite Automata.

Because any non-deterministic finite automaton (with or without instantaneous transitions) can be replaced by a deterministic finite automaton recognizing the same language, from now on we will just say finite automaton (FA for short) instead of DFA, NFA or NFAIT. In practice, we will use

• NFAs or NFAITs for designing an automaton on the paper and then
• DFAs for implementing it on computer.

Indeed, NFAs and NFAITs are easier to manipulate but DFAs are closer to computer programs. Finally we will make the following simplification in the notations for NFAIT: we will denote the non-instaneous transition function and the $\varepsilon$-transition function with the same letter. More precisely, let ($\Sigma$, S, I, T,$\delta$,$\tau$) be a NFAIT. We define for every s $\in$ S

$$\delta \varepsilon \tau$$ (2)

With this convention we can give an unified definition for DFA, NFA or NFAIT.

A FINITE AUTOMATON over $\Sigma$ is a 5-uple ($\Sigma$, S, I, T,$\delta$) where

• S is a finite set, called the set of states of the FA,
• I anf T are non-empty subsets of S, called the sets of the initial states and accepting states of the FA, respectively,
• $\delta$ is a map from S×($\Sigma$ $\cup$ {$\varepsilon$}) to 2^S, called the transition function of the FA.

A non-empty word w = x₁x₂ ^... x_n with length n is recognized by the FA ($\Sigma$, S, I, T,$\delta$) if there exist states s₁, s₂, ^... , s_n-1 $\in$ S such that

1. the state s₁ is an initial state,
2. the state s_i+1 belongs to $\delta$(s_i, x_i) for i = 1 ^... n-1,
3. the state s_n-1 is an accepting state.

The empty word w = $\varepsilon$ is recognized by the above FA if

• either I $\cap$ F $\neq$ $\emptyset$
• or there exists an initial state s such that $\delta$(s,$\varepsilon$) is an accepting state.