CSTheoryFinalExam

HomePage | RecentChanges | Preferences

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.

Chapter 12

If P then Q

If not P, then not Q (contrapositive)

We know the halting problem is [not decidable?]. You can say 'yes' if it halts, but if it hasn't halted yet, you can't say whether it ever will.

For a given program and a given input, you can usually tell whether it will halt or not. You can detect loops by seeing if you're in the same state with the same input. Turing Machines are deterministic, so if you've been in that state with that input before, it's going to happen again.


HomePage | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited December 7, 2006 9:56 am by WendySmoak (diff)
Search: