Nondeterministic Finite Automaton

automata-theory

Definition

Nondeterministic Finite Automaton

A Nondeterministic Finite Automaton (NFA) is a finite automaton that has a nondeterministic transition function.

A nondeterministic transition function is a function that takes a state and an input symbol and returns a set of possible next states.

$$\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$$

where:

• $Q$ is a finite set of states,
• $\Sigma$ is the input alphabet,
• $\delta :Q\times \Sigma \to \mathcal{P}(Q)$ is the transition function (power set of $Q$)
• $q_0\in Q$ is the initial state, and
• $F\subseteq Q$ is the set of accepting (final) states (subset of $Q$).

It processes input symbols (or strings) by transitioning between states according to $\delta$ and determines acceptance based on whether the final state is in $F$.

Determinisation

Definition

Determinisation

Nondeterministic finite automata can be transformd into deterministic finite automata using the method of determinisation.

For a given nondeterministic finite automaton $\mathcal{A}$:

$$\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)\text{with}\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times Q$$

find a deterministic finite automata $\hat{\mathcal{A}}$:

$$\hat{\mathcal{A}}=(\hat{Q},\Sigma ,\hat{\delta },\widehat{q_0},\hat{F})\text{with}\delta \subseteq \hat{Q}\times \Sigma \times \hat{Q}$$

such that $\mathcal{A}$ and $\hat{\mathcal{A}}$ are equivalent, meaning that they accept the same language.

Link to original