Unique finite automaton

The unique finite state machine ( English unambiguous finite automaton , UFA ) takes its position between the deterministic finite-state machine ( DEA , engl. DFA) and the non-deterministic finite automaton ( NFA , engl. NFA) a.

A UFA is basically an NFA, with the restriction that for each input word only one path through the states can lead to the set of accepting states. Like the NFA, the UFA is also nondeterministic and may leave a state in several ways with the same symbol.

Formal definition

Let = an NFA. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \left(Q,\Sigma ,\delta ,q_{0},F\right)}$

• ${\displaystyle Q}$ is a finite set of states.
• ${\displaystyle \Sigma }$ is the input alphabet.
• ${\displaystyle \delta :Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$
• ${\displaystyle q_{0}\in Q}$ is the start state.
• ${\displaystyle F\subseteq Q}$ is a (finite) set of possible accepting states.

${\displaystyle {\mathcal {M}}}$ is a UFA if and only for everyone

• ${\displaystyle x,y\in \Sigma ^{*}}$,
• ${\displaystyle q_{1},q_{2}\in Q}$,
• ${\displaystyle f_{1},f_{2}\in F}$ applies

${\displaystyle (q_{0},xy)\rightarrow ^{*}(q_{1},y)\rightarrow ^{*}(f_{1},\epsilon )}$

${\displaystyle \Rightarrow q_{1}=q_{2}}$

${\displaystyle (q_{0},xy)\rightarrow ^{*}(q_{2},y)\rightarrow ^{*}(f_{2},\epsilon )}$

annotation

The formal definition says that with the UFA, two different intermediate states may not be reached for any word that is accepted by the machine.