The FA formalism provides us with tools to finitely define certain languages: Such a language—defined as an *L*(*M*) over some alphabet *A*, for some FA *M*—contains a string *x* iff there is an *accepting computation*

or, equivalently an *accepting path* within the FA (given as a flow diagram) whose labels from left to right form *x.*

The computation (1) above, equivalently, the path labeled *x* within the FA, are uniquely determined by *x* since the automaton’s *δ*—the *transition relation*—is a total *function.*

Much is to be gained in theoretical flexibility if we relax both the requirements that *δ* is single-valued (a function) and total.

This gives rise to a *nondeterministic* model of finite automata, a “NFA”, that may accept a string in more than one ways, that is, there may be more than one distinct paths from *q*_{0} to an accepting state *q*, each labeled by the same string *x.*

Indeed, even more flexibility is attained if we also allow *“unconditional jumps“* from one state to another, such as

which, in the first approximation, will have unlabeled edges as above. However, in order to retain the central property that we may “read off” what string is accepted by any given ...

Start Free Trial

No credit card required