COT 4210 Homework Fall 2010

• DFAs, NFAs
• Pumping Lemma
• Context Free Grammars
• Turing Machines
• Decidability
• Reducibility
• P, NP
• More P, NP