Math and science::Theory of Computation

Nondeterministic finite automata (NFA)

Nondeterministic finite automata definition

A nondeterministic finite automaton is a 5-tuple $(Q, Σ, δ, q_{0}, F)$ , where

$Q$ is a finite set called the states,
$Σ$ is a finite set called the alphabet,
[...] is the transition function,
$q_{0} \in Q$ is the start sate, and
$F \subseteq Q$ is the set of accept states.

String acceptance

Let $M = (Q, Σ, δ, q_{0}, F)$ be a NFA, let $w$ be a string over the alphabet $Σ$ , and let $Σ_{ε} = Σ \cup {ε}$ (where $ε$ represents [...]).

Then

M

accepts

w

iff we can write

w = y_{1} y_{2} . . . y_{m}

where

y_{i} \in Σ_{ε}

and there exists a sequence of states in

Q

r_{0}, r_{1}, . . ., r_{m}

, meeting three conditions:

$r_{0} = q_{0}$
[...]
$r_{m} \in F$

$w$ is rejected iff it is not accepted.

Every nondeterministic finite automaton has an equivalent [...] (two machines are equivalent iff they recognize the same language). The proof of this is worth studying.

23.03.2020