RPI Study Group

CSCI 2400 Models of Computation

Homework

• Homework 1 - Spring 2009
• Homework 2 - Spring 2009
• Homework 3 - Spring 2009
• Homework 4 - Spring 2009
• Homework 5 - Spring 2009
• Homework 6 - Spring 2009
• Homework 7 - Spring 2009
• Homework 8 - Spring 2009
• Contribute

Lecture Notes

• Intro
• Mathematical Preliminaries
• Finite Automata
• Non-Deterministic Finite Automata
• NFAs and Regular Languages
• Regular Expressions
• Non-Regular Languages
• More Applications of the Pumping Lemma
• Context-Free Languages
• Simplifications of Context-Free Grammars
• Pushdown Automata
• PDAs Accept Context-Free Languages
• The Pumping Lemma for Context-Free Languages
• Even More Applications of the Pumping Lemma
• Turing Machines
• Variations of Turing Machines
• A Universal Turing Machine
• Recursively Enumerable and Recursive Languages
• Linear Bounded Automata
• Reducibility
• Undecidable Problems for Recursively Enumerable Languages
• Time Complexity
• Polynomial Time Reductions
• Polynomial Time Reductions
• Intro
• Mathematical Preliminaries
• Finite Automata
• Non-Deterministic Finite Automata
• NFAs and Regular Languages
• Regular Expressions
• Non-Regular Languages
• More Applications of the Pumping Lemma
• Context-Free Languages
• Simplifications of Context-Free Grammars
• Pushdown Automata
• PDAs Accept Context-Free Languages
• The Pumping Lemma for Context-Free Languages
• Even More Applications of the Pumping Lemma
• Turing Machines
• Variations of Turing Machines
• A Universal Turing Machine
• Recursively Enumerable and Recursive Languages
• Linear Bounded Automata
• Reducibility
• Undecidable Problems for Recursively Enumerable Languages
• Time Complexity
• Polynomial Time Reductions
• Polynomial Time Reductions
• Contribute