[Overview] [Previous] [Next]

Accepting Strings

The (regular) language accepted by a dfa M is

L(M) = {w is a member of sigmastar: deltastar(q0, w) is a member of F}.

The (regular) language accepted by an nfa M is

L(M) = {w is a member of sigmastar: deltastar(q0, w) intersection F not equal to null set}


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

L(M) = {w is a member of sigma*: (q0, w, z) move zero or more times to (p, empty string, u), p is a member of F, u is a member of gamma*}.


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 is a member of sigma+: q0w move zero or more times to xiqfxj
for some qf is a member of F, xi, xj is a member of gamma*}


Copyright 1996 by David Matuszek
Last modified Apr 24, 1996