CMSI 385
Introduction to the Theory of Computation
Fall 2018
- Note
- This page is maintained as an archival record of the course shown above, and as such, some links on this page may no longer be valid nor accessible. They are kept here as a record of the resources that were available at the time of the course offering.
In recognition of Dr. Philip Dorin’s seminal run of teaching this course for nearly 47 years, here is a link to his original syllabus for this course. My own final syllabus isn’t much different in substance, but just mostly reformatted to resemble my other classes.
- Brightspace: Where you can access class screengrab video links and check your grades
- Ars Digita University Theory of Computation playlist: A very accessible collection of video lectures by Prof. Shai Simonson, recorded for Ars Digita University
- How to Ask Questions the Smart Way: Follow these tips to improve the quality and efficiency of the help that you get
- Dr. Philip Dorin’s email screed: A practical companion to “How to Ask Questions the Smart Way,” appropriate not only for email but all electronic text-based communication in general
Assignments
Please see this Brightspace announcement for instructions on accessing the other assignments for this course.
- Assignment 0911 YouTube account listing: 10 points
Video Links and Takeaway Notes
Finite state automata (9 parts)
- Takeaway notes: Finite state automata
- Video example: DFA for binary strings with an even number of zeroes
- Video example: DFA for binary strings with an even number of zeroes and an even number of ones
- Video example: DFA for strings that represent a binary number that is divisible by 4
- Video example:
DFA for binary strings
that contain the substring
110110 - Video example:
DFA for binary strings
for which every
1is followed by at least two0s - Video example: DFA for strings that represent a binary number that is not divisible by 3 (continues into the next video)
- Video example:
Introduction to
non-determinism, followed by NFA for binary strings that contain the substring
110110(continues into the next video) - Video example:
NFA for binary strings
that end in two
0s (continues into the next video) - Video example: Converting an NFA into an equivalent DFA (continues into the next video)
Closure and nondeterminism (9 parts)
- Takeaway notes: Closure and nondeterminism
- Video example review:
DFA for binary strings
for which every
1is followed by at least two0s - Video example:
NFA for the reverse
of binary strings for which every
1is followed by at least two0s (i.e., every1is preceded by at least two0s) (continues into the next video) - Video example review: Converting a constructed NFA for a reverse language into a DFA (which is really just converting an NFA into an equivalent DFA) (continues into the next video)
- Video example: Constructing an NFA that accepts the language which is the union of two other languages, given that you have the machines for those languages
- Video example: Constructing an NFA that accepts the language which is the concatentation of two other languages, given that you have the machines for those languages (continues into the next video)
- Video example: Constructing an NFA that accepts the language which is the intersection of two other languages, given that you have the machines for those languages
The pumping lemma (10 parts)
- Takeaway notes: Regular sets/languages/expressions
- Video shortcut: Statement of the pumping lemma (continues into the next video)
- Video example: Using the pumping lemma to show that the set of palindromes is not regular (continues into the next video)
- Video example: Using the pumping lemma to show that the set of strings whose length is a perfect square is not regular (continues into the next video)
- Video example: Attempted use of the pumping lemma to show that the set of strings whose length is a composite number is not regular (spoiler alert: pumping lemma doesn’t work, and an alternative way needs to be found)
- Video example:
Use of closure and
proof by contradiction to show that the set of strings with equal numbers of
0s and1s is not regular (with help from previous knowledge of other languages) - Video example: Using the pumping lemma to show that a particular scheme for encoding a finite state machine as a string is not regular (you may need to replay the encoding scheme a few times to completely get it; also, includes fun story diversion)
- Video shortcut: Equivalency of DFAs, NFAs, regular expressions, and right-linear grammars
- A fun distraction: Regex Golf
Minimizing finite state machines (9 parts)
- Video example: Introductory example of finite state machine minimization (continues over multiple videos)
- Video example: Second example of finite state machine minimization (continues over multiple videos)
- Video shortcut: Questions that can be answered about finite state automata (continues into next video)
Context-free languages (8 parts)
- A dire warning on the limitations of regular expressions
- Takeaway notes: Context-free grammars
- Video shortcut: Introduction to context-free grammars
- Video example: Context-free grammar, derivation, parse tree, and ambiguity example (continues into the next two videos)
- Video example: Another CFG/derivation/parse tree/ambiguity example (continues into the next video)
- Video examples: Constructing grammars (semantic meaning for non-terminals; recursive approach) (continues into the next two video)
- Video example: A peek into the other side: a context-sensitive grammar (continues through the end of the lecture)
Context-free languages and compilers (9 parts)
- Takeaway notes: Normal forms and pumping lemma for context-free languages
- Video shortcut: Motivation behind Chomsky normal form (continues into the next video)
- Video shortcut: The actual definition of Chomsky normal form (CNF)
- Video shortcut: Converting context-free grammars to Chomsky normal form (continues through the rest of the video set)
Pushdown machines/automata (9 parts)
- Takeaway notes: Push-down automata
- Video example: A first push-down automaton (continues into the next video)
- Video example: A push-down automaton for palindromes with a central marker (continues into the next video)
- Video example: A push-down automaton for even-length palindromes
- Video example: A push-down automaton for the complement of even-length palindromes (continues into the next video)
Context-free grammars and nondeterministic pushdown machines (9 parts)
More lemmas; the CYK algorithm (10 parts)
Undecidability and context-free languages (8 parts)
The bullseye (10 parts)
Turing machines (10 parts)
- Takeaway notes: Turing machines
- Some fun cultural products of this aspect of theoretical computer science:
- Scooping the loop snooper: theory to the sound of Dr. Seuss
- Lego Turing machines: concrete implementations of an abstract idea (one of many)