An Introduction to Formal Languages and Automata, 7th Edition

14.3 LANGUAGE FAMILIES AND COMPLEXITY CLASSES

In the Chomsky hierarchy for language classification, we associate language families with classes of automata, where each class of automata is defined by the nature of its temporary storage. Another possibility for classifying languages is to use a Turing machine and consider time complexity a distinguishing factor. To do so, we first define the time complexity of a language.

DEFINITION 14.1

We say that a Turing machine M decides a language L in time T(n) if every w in L with |w| = n is decided in T(n) moves. If M is nondeterministic, this implies that for every w ∈ L, there is at least one sequence of moves of length less than or equal to T(|w|) that leads to acceptance, and that the Turing machine ...