History of CSTheoryFinalExam

HomePage | RecentChanges | Preferences

Revision 3 . . December 7, 2006 9:56 am by WendySmoak
Revision 2 . . December 7, 2006 8:37 am by WendySmoak
Revision 1 . . December 1, 2006 3:13 pm by WendySmoak

Difference (from prior major revision) (author diff)

Added: 0a1,15

regular - regular expression, regular grammar, accepted by a DFA, NFA or NFA-lambda

context free - context free grammar, PDA (pushdown automaton)

context sensitive - not covered in detail, rules like Ab = Abb

recursive - Turing machine that always halts, uses final states

recursively enumerable - Turing machine that halts to accept, (no final states) but otherwise either does not halt, or halts abnormally

The complement of a recursive language is recursive. - If it's recursive, it's accepted by a Turing machine that always halts. If you flip the accepting/non-accepting states to get the complement, the machine still always halts, so the complement is recursive.

HomePage | RecentChanges | Preferences