## 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
`1`

is followed by at least two`0`

s - 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
`0`

s (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
`1`

is followed by at least two`0`

s - Video example:
NFA for the
*reverse*of binary strings for which every`1`

is followed by at least two`0`

s (i.e., every`1`

is*preceded*by at least two`0`

s) (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`0`

s and`1`

s 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)