diochnos/teaching/CS3823/2022F

Fall 2022 – CS 3823 Theory of Computation

Course Description

Introduces computation theory including grammars, finite state machines, pushdown automata, and Turing machines.

[Course Description] [Table of Contents] [Top]

Basic Information

Syllabus

The syllabus is available here.

Time and Location

Tuesdays and Thursdays, 4:30pm – 5:45pm, Sarkeys Energy Ctr N0202.

Contact Information

Please see here.

Teaching Assistants

The teaching assistant for the class is:

Zuyuan Zhang (Zuyuan.Zhang-1)

Office Hours

We have office hours at the following times and places (you can also join us via Zoom; please consult Canvas for the Zoom link).

Mondays: 9:30am – 11:00am, 230 Devon Energy Hall (Zuyuan Zhang)
Tuesdays: 1:45pm – 3:00pm, 230 Devon Energy Hall (Dimitris Diochnos)
Wednesdays: 10:30am – 11:30am, 230 Devon Energy Hall (Dimitris Diochnos)
Thursdays: 1:45pm – 3:00pm, 230 Devon Energy Hall (Dimitris Diochnos)
Fridays: 9:30am – 11:00am, 230 Devon Energy Hall (Zuyuan Zhang)

Please note that while anyone is welcome during my office hours (Dimitris Diochnos), students from CS 5970 will have precedence on Wednesdays, while students from CS 3823 will have precedence on Tuesdays and Thursdays.

Exceptions to the Regular Schedule of Office Hours

If you want to meet me outside of my office hours, please send me an email and arrange an appointment.

Thursday, September 29, 2022: I will hold an additional office hour between 3pm-4pm.

Friday, September 30, 2022: I will hold an additional office hour between 1:30pm-2:30pm.

Wednesday, October 3, 2022: I will hold an additional office hour between 1:30pm-2:30pm.

Thursday, October 13, 2022: I will hold office hours between 1:45pm-2:45pm; that is, I will finish 15 minutes earlier this day.

Tuesday, November 15, 2022: I will hold an additional office hour between 3:00pm-4:00pm since the midterm is on Thursday.

Wednesday, November 16, 2022: I will hold additional office hours between 2:00pm-2:45pm since the midterm is on Thursday.

Thursday, November 17, 2022: I will hold an additional office hour between 3:00pm-4:00pm since the midterm is that day.

Exceptions to the Regular Schedule of Office Hours for the TAs

As exceptions appear along the way, they will also be announced here.

[Basic Information] [Table of Contents] [Top]

Homework Assignments (Estimates)

Assignment 1: Announced on Thursday, September 1 (week 2). Due on Friday, September 9 (week 3).

Assignment 2: Announced on Tuesday, September 20 (week 5). Due on Friday, September 30 (week 6).

Assignment 3: Announced on Tuesday, October 18 (week 9). Due on Tuesday, October 25.

Assignment 4: Announced on Tuesday, November 1 (week 11). Due on Friday, November 11 (week 12).

Assignment 5: To be announced on Tuesday, November 29 (week 15). To be due on Tuesday, December 6 (week 16).

[Homework Assignments] [Table of Contents] [Top]

Theory of Computation Resources

Basic Concepts and Notation, by Gabriel Robins.
Think like the pros, by Emanuele Viola.
Who Can Name the Bigger Number?, by Scott Aaronson.
The Physical Origin of Universal Computing, by Michael Nielsen.

[Theory of Computation Resources] [Table of Contents] [Top]

Class Log

A log for the class will be held online here.

Week 1

Class 1 (Aug 23, 2022)

Discussion on syllabus and policies.

Class 2 (Aug 25, 2022)

Discussion on mathematical background.

We will finish our discussion next time.

Week 2

Class 3 (Aug 30, 2022)

Introduction to deterministic finite automata. Examples, their description, defining computation, definition of regular languages, designing finite automata according to specifications.

Introduction to regular operations. Next time we will prove that regular languages are closed under union and intersection.

Class 4 (Sep 1, 2022)

Proved that regular languages are closed under union and intersection.

Started discussion on non-determinism. Multiple transitions for the same symbol, missing transitions for some symbols, transitions triggered on empty input (λ).

Example NFA with a complete run on a specific input exhibiting the behavior of the above concepts. We will conclude next time.

Assigned today: Homework 1. (Due: Fri, Sep 9)

Week 3

Class 5 (Sep 6, 2022)

Example NFA with a complete run on a specific input exhibiting the behavior of the above concepts.

Designing an NFA for a specific language in mind (having a 1 three positions from the end of the binary string); then doing so also with a DFA.

Started discussion on the theorem about the equivalence between DFAs and NFAs.

Revising some concepts from discrete mathematics; induction, Gauss' trick and extension to geometric series.

Class 6 (Sep 8, 2022)

Discussion on TeX/LaTeX. History, evolution, creators, usage.

Continued our discussion on the theorem about the equivalence between DFAs and NFAs.

This time we proved the theorem that we stated last time.

Friday, September 9, 2022

Due today: Homework 1.

Week 4

Class 7 (Sep 13, 2022)

Closure under the regular operations. We looked into union, concatenation, star.

Started our discussion on regular expressions.

September 15, 2022

No class due to a career fair.

Week 5

Class 8 (Sep 20, 2022)

Discussion on homework assignments, midterm, and the meaning of closure for regular operations. For this last point we also had a glimpse on the big picture behind languages that we will explore in this class: regular, context-free, Turing decidable, Turing recognizable, Turing unrecognizable. We will be familiar with these notions in November.

Continued our discussion on regular expressions. Proved that a language described by a regular expression can be recognized by an NFA and we also saw some examples.

Assigned today: Homework 2.

Class 9 (Sep 22, 2022)

The first midterm will take place on Thursday, October 6.

Discussed the conversion of regular languages to regular expressions.

In this direction we discussed generalized transition graphs (GTGs) / generalized non-deterministic finite automata (GNFAs) and described the procedure that can take any DFA to a GNFA and then reducing that GNFA from k nodes to a GNFA with just two nodes (start state and accept state). The label of the arrow connecting these two states is the regular expression that we want.

We saw two examples for this reduction.

Week 6

Class 10 (Sep 27, 2022)

Announced office hours for this and the following week via email. An announcement is also made above on this webpage.

Announced material that will be in the coming midterm exam via email.

Verified the above announcements in class.

The pumping lemma for regular languages. Examples uses for proving non-regularity of certain languages.

Class 11 (Sep 29, 2022)

More examples on the use of pumping lemma for proving non-regularity of certain languages.

Sep 30, 2022

Due today: Homework 2.

Week 7

Class 12 (Oct 4, 2022)

Discussion on homework and answering students' questions.

Preparation for the midterm.

Class 13 (Oct 6, 2022)

First midterm exam.

Week 8

Class 14 (Oct 11, 2022)

Started the discussion on context-free grammars.

Designing CFGs - among others, how to convert a DFA to a CFG (which, btw, shows that RLs ⊆ CFLs; that is, regular languages are a subset of context-free languages – we can combine this information with the fact that among CFLs we can find languages that are not regular, e.g., {0ⁿ1ⁿ | n ≥ 0}, and conclude that RLs ⊊ CFLs; that is, regular languages form a proper subset of context free languages).

Class 15 (Oct 13, 2022)

Ambiguous grammars, inherently ambiguous languages.

Chomsky Normal Form for CFGs. We started discussing an example but we ran out of time. Next time we will finish with the example.

Week 9

Class 16 (Oct 18, 2022)

Midterm returned. Discussion on the solutions of the midterm.

Assigned today: Homework 3. Due on Tuesday, October 25.

Class 17 (Oct 20, 2022)

We finished with the example on Chomsky Normal Form.

We discussed (nondeterministic) pushdown automata (PDAs). How they perform computation and we also saw examples.

Week 10

Class 18 (Oct 25, 2022)

Continued our discussion on (nondeteterministic) pushdown automata (PDAs). Examples using PDAs.

Due today: Homework 3. Pushed back to Oct 27.

Class 19 (Oct 27, 2022)

MoneyCoach presentation by Cami Sheaffer.

Due today: Homework 3.

Week 11

Class 20 (Nov 1, 2022)

Pumping lemma for context-free languages and one example.

Assigned today: Homework 4. Due, Friday, November 11.

Class 21 (Nov 3, 2022)

More examples on the use of the pumping lemma for context-free languages in order to prove that said languages are not context-free.

Introduction to Turing machines: notation, the 7-tuple, configurations.

Week 12

Class 22 (Nov 8, 2022)

Designing TMs, state diagrams of TMs, defining decidable and recognizable languages.

Example of a state diagram for a Turing machine - deciding the language {0^2ⁿ | n ≥ 0}.

Class 23 (Nov 10, 2022)

One more example deciding the language {aⁱb^jc^k | i × j = k and i, j, k ≥ 1}.

Discussion on recognizable vs decidable languages. Hilbert's 10th problem.

Three different levels of description of a TM. We looked into the language B = {w#w | w ∈ {0,1}^*} and three different ways of describing the TM that decides this language.

We had a discussion about the big picture of things: proper subset relations between different classes of languages. How the pumping lemmas fit into this picture.

Discussion on finding the roots of univariate and multivariate polynomials. Discussed the sum of three cubes being equal to 42. Hilbert's tenth problem is recognizable but not decidable. We also mentioned that there are problems that are not even recognizable - we will see such an example in the future.

Complexity theory cares about decidable languages. There we find different classes, such as P, NP, PSPACE, etc. Of particular interest are the classes P and NP.

Friday, November 11, 2022

Due today: Homework 4.

Week 13

Class 24 (Nov 15, 2022)

Discussion on homework and answering students' questions.

Preparation for the midterm.

Class 25 (Nov 17, 2022)

Second midterm exam.

Week 14

Class 26 (Nov 22, 2022)

Equivalence of different models of Turing machines; multi-tape, nondeterministic, TMs that have the option to stay put, etc.

Nov 24, 2022

Thanksgiving; no class.

Week 15

Class 27 (Nov 29, 2022)

Discussion on the big picture for the Chomsky hierarchy of languages.

A_DFA, A_NFA, A_REX, E_DFA, EQ_DFA, A_CFG are decidable languages. There is one or two more languages discussed in the notes that I did not cover in class – you do not have to read them, though for the largest part their proofs are easy and it would not hurt at least skimming through their text.

Brief recap of set theoretic notions.

Announce, in-class, homework 5. Will be due on Tuesday, December 6th.

Assigned today: Homework 5. Due, Tuesday, December 6.

Class 28 (Dec 1, 2022)

The acceptance problem, A_TM, is undecidable.

Co-Turing recognizable languages and Turing unrecognizable languages.

A_TM is not Turing recognizable.

High level discussion on reductions.

HALT_TM is undecidable (reduction from A_TM).

The Post Correspondence Problem. You should know what the problem is and that it is undecidable.

Rice's Theorem.

Introduction, overview of complexity theory and some related problems.

Complexity classes P and NP.

Week 16

Class 29 (Dec 6, 2022)

Returning second midterm to students and discussing the solutions for that midterm.

Due today: Homework 5.

Class 30 (Dec 8, 2022)

Solutions to homework 5. Perhaps some additional discussion on review problems as preparation for the final.

Problems that are complete for a class and discussion on NP-Complete problems.

The million-dollar question: P vs NP.

You can find the list with the seven open problems (each one of them pays one million dollars) of the Clay Mathematics Institute here.

Week 17

Monday, December 12, 2022 (4.30pm – 6.30pm)

Final exam. In-class (Sarkeys Energy Ctr N0202 — where we met throughout the semester).

Dimitris Diochnos

Δημήτρης Διώχνος