الرئيسية
المنتديات
الانتساب : 
العمر : 
المساهمات : 
نقاط التميز
Theory of Computation
محاظرات من جامعة
كل جابتر بملف وورد منفصل ..
Binghamton University
Chapter 1 - Introduction to the Theory of Computation
Covers: Mathematical preliminaries, notation, and basic concepts and other cool but hairy stuff
... set theory, graph theory, proof techniques, languages, grammars, the concept of an automaton.
Last updated: 1/27/03
Chapter 2 - Finite Automata
Covers: Deterministic Finite Accepters (DFA's), Nondeterministic Finite Accepters (NFA's), and equivalence of DFA's and NFA's. Note: when a cross-reference to the text is given, the reference in parenthesis is for the 2nd edition.
Last updated: 1/31/03, small typo in algorithm for NFA->DFA conversion fixed 3/4/03
Supplemental Materials:
Some Notes on Lambda Transitions
Last updated: 09/15/00
Chapter 3 - Regular Languages and Regular Grammars
Covers: Regular expressions, connection between regular expressions and regular languages, and regular grammars
Last updated: 2/7/03
Supplementary Notes for chapter 3 by N. Guydosh- Updated 9/28/03
Chapter 4 - Properties of Regular Languages
Covers: Closure properties of regular languages, elementary
questions about regular languages, identifying regular languages,
pigeonhole principle, and pumping lemma for regular languages
Last updated:3 /10/02
Details of examples in chapter 4
Comments on the use of the pumping lemma for regular languages - by N. Guydosh, updated 10/1/03
Chapter 5 - Context-Free Languages
Covers: Context-free grammars, parsing, ambiguity, and context-free grammars and programming languages
Last updated: 10/12/03
Chapter 6 - Simplification of Context-Free Grammars and Normal Forms
Covers: Methods for transforming grammars, Chomsky Normal Form (CNF), and Greibach Normal Form (GNF)
Last updated: 3/19/01
Ouline of procedures for removing useless, lambda, and unit prroductions -
Chapter 7 - Pushdown Automata
Covers: Nondeterministic Pushdown Automata (NPDA's), pushdown
automata and context-free languages, and deterministic pushdown automata
and deterministic context-free languages
Last updated: 3/30/03
Chapter 8 - Properties of Context-Free Languages
Covers: Pumping lemma for context-free languages, closure
properties and decision algorithms for context-free languages, and
properties of context-free languages
Supplementary Notes Used in Class
Examples of the CFL Pumping Lemma From Kozen's Book From Brett Bernstein 4/11/03
Sample Pumping Lemma Problem 8.1.4a Last updated: 11/07/00
Sample Pumping Lemma Problem 8.1.4d Last updated: 11/24/00
Chapter 9 - Turing Machines
Covers: Definition of a Turing Machine, Turing Machines as language accepters, combining Turing Machines, Turing's thesis
Last updated: 11/6/03
Turing Machine Examples
Last updated: 11/6/03
Chapter 10 - Other Models of Turing Machines
Covers: Equivalence of classes of automata, Turing Machines with a
Stay-Option, Turing Machines with a semi-infinite tape, Turing Machines
with more complex storage4, non-deterministic Turing Machines,
universal Turing Machines
Last updated: 4/21/03
Chapter 11 - A Hierarchy of Formal Languages and Automata
Covers: Recursive and recursively enumerable languages,
unrestricted grammars, context-sensitive grammars and languages, the
Chomsky Hierarchy
Last updated: 11/18/03
Summary of ideas on Recursively Enumerable Languages and Corresponding Grammars - Updated 12/15/02
Comments on Recursively Enumerable vs. Countable- Updated 12/11/03
Chapter 12 - Limits of Algorithmic Computation - The Halting Problem
Covers: Decidability and computability, problems that cannot be
solved by Turing Machines, The Turing Machine halting Problem, proof
that the halting problem is NOT decidable.
Last updated: 12/13/00
Summary of ideas on the Halting Problem - Updated 12/15/02
Relationship Between the Halting Problem and Recursively Enumerable Languages - NEW
محاظرات من جامعة
كل جابتر بملف وورد منفصل ..
Binghamton University
Chapter 1 - Introduction to the Theory of Computation
Covers: Mathematical preliminaries, notation, and basic concepts and other cool but hairy stuff
... set theory, graph theory, proof techniques, languages, grammars, the concept of an automaton.
Last updated: 1/27/03
Chapter 2 - Finite Automata
Covers: Deterministic Finite Accepters (DFA's), Nondeterministic Finite Accepters (NFA's), and equivalence of DFA's and NFA's. Note: when a cross-reference to the text is given, the reference in parenthesis is for the 2nd edition.
Last updated: 1/31/03, small typo in algorithm for NFA->DFA conversion fixed 3/4/03
Supplemental Materials:
Some Notes on Lambda Transitions
Last updated: 09/15/00
Chapter 3 - Regular Languages and Regular Grammars
Covers: Regular expressions, connection between regular expressions and regular languages, and regular grammars
Last updated: 2/7/03
Supplementary Notes for chapter 3 by N. Guydosh- Updated 9/28/03
Chapter 4 - Properties of Regular Languages
Covers: Closure properties of regular languages, elementary
questions about regular languages, identifying regular languages,
pigeonhole principle, and pumping lemma for regular languages
Last updated:3 /10/02
Details of examples in chapter 4
Comments on the use of the pumping lemma for regular languages - by N. Guydosh, updated 10/1/03
Chapter 5 - Context-Free Languages
Covers: Context-free grammars, parsing, ambiguity, and context-free grammars and programming languages
Last updated: 10/12/03
Chapter 6 - Simplification of Context-Free Grammars and Normal Forms
Covers: Methods for transforming grammars, Chomsky Normal Form (CNF), and Greibach Normal Form (GNF)
Last updated: 3/19/01
Ouline of procedures for removing useless, lambda, and unit prroductions -
Chapter 7 - Pushdown Automata
Covers: Nondeterministic Pushdown Automata (NPDA's), pushdown
automata and context-free languages, and deterministic pushdown automata
and deterministic context-free languages
Last updated: 3/30/03
Chapter 8 - Properties of Context-Free Languages
Covers: Pumping lemma for context-free languages, closure
properties and decision algorithms for context-free languages, and
properties of context-free languages
Supplementary Notes Used in Class
Examples of the CFL Pumping Lemma From Kozen's Book From Brett Bernstein 4/11/03
Sample Pumping Lemma Problem 8.1.4a Last updated: 11/07/00
Sample Pumping Lemma Problem 8.1.4d Last updated: 11/24/00
Chapter 9 - Turing Machines
Covers: Definition of a Turing Machine, Turing Machines as language accepters, combining Turing Machines, Turing's thesis
Last updated: 11/6/03
Turing Machine Examples
Last updated: 11/6/03
Chapter 10 - Other Models of Turing Machines
Covers: Equivalence of classes of automata, Turing Machines with a
Stay-Option, Turing Machines with a semi-infinite tape, Turing Machines
with more complex storage4, non-deterministic Turing Machines,
universal Turing Machines
Last updated: 4/21/03
Chapter 11 - A Hierarchy of Formal Languages and Automata
Covers: Recursive and recursively enumerable languages,
unrestricted grammars, context-sensitive grammars and languages, the
Chomsky Hierarchy
Last updated: 11/18/03
Summary of ideas on Recursively Enumerable Languages and Corresponding Grammars - Updated 12/15/02
Comments on Recursively Enumerable vs. Countable- Updated 12/11/03
Chapter 12 - Limits of Algorithmic Computation - The Halting Problem
Covers: Decidability and computability, problems that cannot be
solved by Turing Machines, The Turing Machine halting Problem, proof
that the halting problem is NOT decidable.
Last updated: 12/13/00
Summary of ideas on the Halting Problem - Updated 12/15/02
Relationship Between the Halting Problem and Recursively Enumerable Languages - NEW
