The (regular) language accepted by a dfa M is

L(M) = {w
:
(q_{0},
w) F}.

The (regular) language accepted by an nfa M is

L(M) = {w
:
(q_{0},
w) F
}

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

L(M) = {w
*: (q_{0}, 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_{0}w
x_{i}q_{f}x_{j}

for some q_{f}
F, x_{i}, x_{j}
*}

Copyright © 1996 by David Matuszek

Last modified Apr 24, 1996