O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

3.2   NONDETERMINISTIC FINITE AUTOMATA

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

Images

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

Images

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

Images

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required