Theory of Computation

Syllabus

Calendar:

The calendar on the syllabus is the plan for this semester, this calendar reflects in detail what we actually get to cover in class and when.

  • …
  • 4-22-2024: Exam 2
  • 4-15-2024: Started material on Unit 3
  • 4-8-2024: Completed Slides on Limits of Turing Machines. Next week we will start Unit 3 material.
  • 4-1-2024: Handed back the exam. Discussed Turing Machines and their limitations. We will have a quiz on 4-8-2014. Also, now would be a good time to tackle the Exploring Infinity extra credit assignment.
  • 3-25-24: Exam 1
  • 3-18-24: We started material from Unit 2. Next week, Monday 3-25-24, we will start by answering review questions you bring in. Then, after a short break, we will have exam 1.
  • 3-4-24: We finished off Unit 1.
  • 2-26-24: We finished most, but not all of the work for Unit 1. Since we didn’t quite get through it all, the exam will be pushed to 3/25, but we will still be starting the next unit on 3/18. Next week we will have a quiz, finish up Unit 1, and maybe touch on Unit 2. You should also be turning in the first assignment next week, this needs to be typed and in complete sentences.
  • 2-19-24: Presidents’ Day Break
  • 2-12-24: We looked at a couple more examples of non-regular language; we have looked at four or five examples of using the pumping lemma to show a language is non regular, you should be seeing the pattern in these sorts of questions now. We then started discussing Context-Free Grammars by looking at basic examples like some of those in the text and looking at the Ascii Math Handout. We then briefly introduced the Chomsky Normal Form. For the Quiz next week you should know what the Chomsky Normal Form is, but don’t worry about converting an arbitrary grammar to it; we will look at some examples next class.
  • 2-5-24: Tonight we finished our discussion of DFAs and NFAs and then moved on to Regular Expressions. In particular we looked at how we could translate any NFA into a GNFA and then to a Regular Expression; we concluded that a language is regular if and only if it can be expressed with a regular expression. We then discussed the pumping lemma and looked at two examples of non-regular languages. After the quiz next week we will look at another non-regular language before moving onto a new topic.
  • 1-30-24: Tonight we covered the first three sections of the slides on Finite Autamata, you should review these sections for next weeks quiz.
  • 1-22-24: Tonight we went over the syllabus and covered the Review Material (updated) slides.

Assignments:

All out of class work in this class must be typed up and in complete sentences.

  • Chapter 1: p.83 – 1.3, 1.4c, 1.5c, 1.6ej, 1.12, 1.18ej, 1.21b, 1.22, 1.28a, 1.29b Due 2/26/2024 3/4/2024
  • Chapter 2: p. 154: 2.1, 2.2, 2.4bc, 2.5bc, 2.11, 2.13, 2.14, 2.15, 2.16 Due 3/25/2024
  • Chapter 3: p.187: 3.1cd, 3.2cd, 3.8b, 3.9, 3.15bc, 3.16bc Due 4/15/2024
  • Chapter 4: p.210: 4.3, 4.4, 4.6 4.7 4.11, 4.13 Due 4/29/2024
  • Chapter 5: Chapter 5: p.239 – 5.1 (use Theorem 5.13 and show that \(ALL_{CFG}\leq_m EQ_{CFG}\)), 5.2 (Show, directly, that  \(\overline{EQ}_{CFG}\) is recognizable); Chapter 6: p.270 – 6.1, 6.11 (look at 6.10), 6.28 (look at 6.12) Due 5/10/2024 by 3pm
  • Extra Credit: Turing Machine Class Due 5/10/2024 by 3pm
  • Extra Credit: Exploring the Infinite Due 5/10/2024 by 3pm

Exam Guides:

Unit 1: Automata and Languages Exam (Chapters 1& 2) (Exam date moved to 3/25!!!)

  • Definitions: Deterministic and Non-Deterministic Finite State Automata, Regular Languages, Unions, Concatenation, Star Operation, Generalized Non-Deterministic Finite State Automata, Regular Expressions, Pumping Lemma, Context Free Grammars, Parse Tree, Chomsky Normal Form, Pushdown Automata, …
  • Be Able To:
    • Create basic NFAs or DFAs to recognize simple languages
    • State explicitly \(A\cup B\), \(A\circ B\), \(A^*\), and \(A^+\) for small sets \(A\) and \(B\)
    • Simplify a GNFA to create a regular expression
    • Apply to Pumping Lemma for regular languages to show a language is not regular
    • Identify Context Free Grammar and make “simplifications” to it to change it to Chomsky Normal Form
    • Write a parse tree for an expression based on a grammar
    • Read and explain the action of a Pushdown Automata

Unit 2: Computability Theory Exam 1 (Chapters 3 & 4) (Exam Moved to 4/22/2024)

  • Definitions: Turing Machine, Formal, Implementation, and High-Level Descriptions, Multitape Turing Machine, Enumerator, Algorithm, Decidable Language, Recognizable Language, Regular Language, Context Free Language, Cardinality of a Set, Power Set, …
  • Be Able To:
    • Read a diagram of a Turing Machine,
    • Follow a High-Level Description of a Turing Machine
    • Organize the different categories of languages
    • Describe the diagonalization process
    • Explain why two sets are the same cardinality
    • Describe the power set of a set

Unit 3: Computability Theory Exam 2 (Chapters 5 & 6) (Exam Cancelled)

  • Definitions: Turing Recognizable and co-Recognizable, Reducible, Computable Function, Mapping Reducible, Computational History, linear bounded automaton, Self Replicating, Recursion, Universal Quantifier, Existential Quantifier, Model, Theory, Provability, Oracles, Turing Decidable, Turing Reduction, Information, Minimal Description, Descriptive Complexity, Compressible,
  • Be Able To:
    • Demonstrate understanding of predicates, quantifiers, and what it means for a statement to be true,
    • Read a diagram of a Turing Machine,
    • Follow a High-Level Description of a Turing Machine,
    • Organize the different categories of languages,
    • Find/Follow the computational history of a Turing Machine

Lecture Slides (2023 Versions)

Links and Handouts: