[Overview] [Previous] [Next]

Accepting Strings

The (regular) language accepted by a dfa M is

L(M) = {w : (q₀, w) F}.

The (regular) language accepted by an nfa M is

L(M) = {w : (q₀, w) F }

The (context-free) language accepted by an npda M is

L(M) = {w *: (q₀, w, z) (p, , u), p F, u *}.

An lba is a Turing machine with a limited amount of tape (a linear function of the size of the input). Lbas accept context-sensitive languages.

The language accepted by a Turing machine M is

L(M) = (w +: q₀w x_iq_fx_j
for some q_f F, x_i, x_j *}