COSC 340: Theory of Computation

Spring 2025

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 Languages Deterministic Finite Automata (DFAs) Nondeterministic Finite Automata (NFAs) Regular Expressions (REGEX) Regular Grammars Context-Free Languages Context-Free Grammars (CFGs) Pushdown Automata (PDA) Deterministic Pushdown Automata (DPDA)
Videos	Coming soon…
Study Guides	Study Guide 1 Study Guide 2
Projects	Project 1 (examples) Project 2 Project 3 (examples) Project 4

Course Schedule

Week	Date	Topics	Due
1	Feb 3rd (Monday)	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 5th (Wednesday)	Math Review For next time: Finish reviewing the material in 0.1 and 0.2. We will start with our first model of computation next time. Brush up on the Python programming language.
	Feb 7th (Friday)	Deterministic Finite Automata (DFAs) For next time: Read 1.1 regarding DFAs. Start working on Project 1.	Read 0.1 and 0.2
2	Feb 10th (Monday)	Deterministic Finite Automata (DFAs) For next time: Finish reading 1.1. Continue working on Project 1 (I strongly suggest to get started early, just in case you run into some problems with your code).
	Feb 12th (Wednesday)	Nondeterministic Finite Automata (NFAs) For next time: Start reading 1.2. Continue working on Project 1. I’ll give you some Python tips for your project on Friday.	Read 1.1
	Feb 14th (Friday)	Nondeterministic Finite Automata (NFAs) For next time: Continue reading 1.2. Continue working on Project 1. You can use the Python tips I provided today, but don’t feel like you have to.
3	Feb 17th (Monday)	Nondeterministic Finite Automata (NFAs) For next time: Finish reading 1.2. Finish Project 1.
	Feb 19th (Wednesday)	Regular Expressions (REGEX) For next time: Start reading 1.3. Finish Project 1 tonight. Project 2 will be assigned next time.	Project 1 Read 1.2
	Feb 21st (Friday)	Regular Expressions (REGEX) For next time: Continue reading 1.3. Project 2 is now assigned.
4	Feb 24th (Monday)	Regular Expressions (REGEX) For next time: Finish reading 1.3. Continue working on Project 2. Check out the “RegExr” tool posted above.
	Feb 26th (Wednesday)	Nonregular Languages (The Pumping Lemma) For next time: I will be at a conference on Thursday and Friday, so we will not have class Friday. Keep working on Project 2. I’m going to go ahead and post Project 3 for anyone that wants to get a head start on it.	Read 1.3
	Feb 28th (Friday)	SIGCSE 2025 - NO CLASS
5	Mar 3rd (Monday)	Nonregular Languages (The Pumping Lemma) For next time: Since I was gone, I will give you two extra days on Project 2 (it’s now due Wednesday night). So keep working on Project 2, and feel free to get a head start on Project 3. Our first exam will be Monday next week, and we will review on Wednesday.
	Mar 5th (Wednesday)	Review for Exam 1 For next time: Study for Exam 1, which will be on Monday. Finish Project 2 tonight, and start on Project 3.	Project 2 Read 1.4
	Mar 7th (Friday)	NO CLASS For next time: Exam 1 is on Monday. Turn your attention to studying for it, and then to working on Project 3.
6	Mar 10th (Monday)	Exam 1 For next time: Working on Project 3 (this one is trickier than Project 1!).
	Mar 12th (Wednesday)	Context-Free Grammars (CFG) For next time: I’m moving Project 3 a bit to give you more time to work on it (it’s challenging). Start reading 2.1.
	Mar 14th (Friday)	Context-Free Grammars (CFG) For next time: Keep working on Project 3. I’ll give some hints regarding it on Monday. Continue reading 2.1.
7	Mar 17th (Monday)	Context-Free Grammars (CFG) For next time: Keep working on Project 3. We will start a new model of a computer next time.
	Mar 19th (Wednesday)	Pushdown Automata (PDA) For next time: Start reading 2.2. Finish Project 3.	Read 2.1
	Mar 21st (Friday)	Pushdown Automata (PDA) For next time: Project 3 is due tonight. Continue reading 2.2. We will finish off PDAs after break.	Project 3
8	Mar 24th (Monday)	SPRING HOLIDAY - NO CLASS
	Mar 26th (Wednesday)	SPRING HOLIDAY - NO CLASS
	Mar 28th (Friday)	SPRING HOLIDAY - NO CLASS
9	Mar 31st (Monday)	Pushdown Automata (PDA) For next time: Project 4 is now assigned. Finish reading 2.2. We will review for Exam 2 next time.	Read 2.2
	Apr 2nd (Wednesday)	Review for Exam 2
	Apr 4th (Friday)	Turing Machines (TMs)
10	Apr 7th (Monday)	Turing Machines (TMs)
	Apr 9th (Wednesday)		Project 4
	Apr 11th (Friday)	Exam 2
11	Apr 14th (Monday)
	Apr 16th (Wednesday)
	Apr 18th (Friday)
12	Apr 21st (Monday)
	Apr 23rd (Wednesday)
	Apr 25th (Friday)
13	Apr 28th (Monday)
	Apr 30th (Wednesday)
	May 2nd (Friday)
14	May 5th (Monday)
	May 7th (Wednesday)
	May 9th (Friday)
15	May 15th (Thursday)	Final Exam (8:00AM - 10:30AM)