COSC 340: Theory of Computation

Spring 2024

Course Resources

General	Syllabus JFLAP (download version 7.1, and either the JRE or the JDK) RegExr: An online tool to learn, build, and test regular expressions
Python Tutorials	python.org w3schools learnpython.org pythontutorial.net
Wikipedia	Regular Language Deterministic Finite Automata (DFAs) Nondeterministic Finite Automata (NFAs) Regular Expression (REGEX) Regular Grammars Context-Free Language Context-Free Grammar (CFGs) Deterministic Pushdown Automata (DPDA) Pushdown Automata (PDA) Recursively-Enumerable Language (Turing-recognizable) Enumerator (a type of Turing Machine) Recursive Language (Turing-decidable) Decider (a type of Turing Machine)
Videos	Mechanical Turing Machine in Wood A Computer That Runs on Marbles LEGO Turing Machine A Turing Machine in the Classic Style On the Turing Completeness of Powerpoint
Study Guides	Study Guide 1 Study Guide 2
Projects	Project 1 (examples) Project 2 Project 3 (examples) Project 4 Project 5 (examples) Project 6 (examples)

Course Schedule

Week	Date	Topics	Due
1	Feb 6th (Tuesday)	Course Introduction / Math Review For next time: Read the syllabus, download and install Java, download JFLAP, get the textbook and start reading Chapter 0 of your textbook (mostly focusing on 0.1 and 0.2), and brush up on Python.
	Feb 8th (Thursday)	Deterministic Finite Automata (DFA) For next time: Start reading Sipser (Chapter 1.1), and brush up on Python.	Read Chapter 0
2	Feb 13th (Tuesday)	Nondeterministic Finite Automata (NFA) For next time: Start reading Sipser (Chapter 1.2). Your first project in now posted.	Read 1.1
	Feb 15th (Thursday)	Regular Expressions (REGEX) For next time: Start reading Sipser (Chapter 1.3). Keep working on your first project.
3	Feb 20th (Tuesday)	Regular Expressions (REGEX) For next time: Keep working on Project 1, and make sure you are caught up on reading 1.1-1.3.	Read 1.2
	Feb 22nd (Thursday)	Nonregular Languages (The Pumping Lemma) For next time: Keep working on Project 1. Project 2 is now posted. Start reading 1.4.	Read 1.3
4	Feb 27th (Tuesday)	Nonregular Languages (The Pumping Lemma) For next time: Finish Project 1. Project 2 and 3 are now both posted. Finish reading reading 1.1-1.4.	Project 1
	Feb 29th (Thursday)	Context-Free Grammars (CFG) For next time: Exam 1 is going to be March 14th. The study guide is posted above. All of the content comes from 1.1-1.3. Continue working on projects 2 and 3.	Read 1.4
5	Mar 5th (Tuesday)	Context-Free Grammars (CFG) For next time: Start reviewing all of the content from 1.1-1.3 for the exam. Finish project 2.
	Mar 7th (Thursday)	Review for Exam 1 For next time: Keep reviewing for the exam. Project 2 is due tonight.	Project 2
6	Mar 12th (Tuesday)	Context-Free Grammars (CFG) For next time: Exam 1 will be Thursday. Remember to review the study guide. I’m moving Project 3 a bit to give you more time to work on it (it’s challenging).	Read 2.1
	Mar 14th (Thursday)	Exam 1
7	Mar 19th (Tuesday)	Pushdown Automata (PDA) For next time: No class on Thursday. Use this time to finish Project 3 and/or start Project 4.
	Mar 21st (Thursday)	No Class (SIGCSE 2024)
8	Mar 26th (Tuesday)	Pushdown Automata (PDA)	Project 3
	Mar 28th (Thursday)	Pushdown Automata (PDA)	Read 2.2
9	Apr 2nd (Tuesday)	No Class (Spring Holiday)
	Apr 4th (Thursday)	No Class (Spring Holiday)
10	Apr 9th (Tuesday)	Review for Exam 2 For next time: Keep reviewing for the exam (the study guide is now posted). Project 4 is due next week. Project 5 is also posted.
	Apr 11th (Thursday)	Turing Machines (TMs)	Read 3.1
11	Apr 16th (Tuesday)	Exam 2	Project 4
	Apr 18th (Thursday)	Turing Machines (TMs)	Read 3.2
12	Apr 23rd (Tuesday)	Decidability	Read 3.3
	Apr 25th (Thursday)	Undecidability	Project 5 Read 4.1
13	Apr 30th (Tuesday)
	May 2nd (Thursday)
14	May 7th (Tuesday)
	May 9th (Thursday)		Project 6
15	May 16th (Thursday)	Final Exam (11:30AM - 2:00PM)