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 q0 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 ...

Get Theory of Computation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.