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

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

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

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

عاشت ايدك كابتن وان شاء الله يحفظك ذخر لطلاب علوم الحاسبات بس عندي طلب من طلاب المرحلة الثانية يريدون بيه الفرق بين (Transtion Graph) & (Finit Automata)

شكراً جزيلاً

شكراااااااااااااااااااااا

يدللوووووو اخواني

طلال و sniperoflove

منورين الموضوع

نتمنى ان تتواصلوا

تحياتي لكم

هل ممكن حصولي على حل الاساله الخاصه بكل جابتر الموجوده في كتاب النضريه الاحتسابيه

سلام عليكم اني عضو جديد مرحلة ثاني شككرا على شرح الاحتسابية بس
بس مداخلة السنة الوزارة ضافت الاحتسابية للوزاري يعني اسئلة وزارية للفاينل فممكن محاظرات جامعة بغداد اوكتاب كوهن رجااءاااا [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]