Jay Pantone

Assistant Professor
Marquette University

jay.pantone@marquette.edu


Math 4931 / 5931 – Theory of Computation and Formal Languages

Spring 2023, Marquette University

This course will cover the mathematical foundations of the theory of computation, a branch of mathematics and computer science focused on different models of computation and their ability to solve problems. Possible topics may include: finite state automata and regular expressions; push down automata and context-free grammars; Turing machines and the Church-Turing thesis; computability; undecidability; and Godel's Incompleteness Theorem. The course will also include applications of several of these topics to other areas, particularly the mathematical field of combinatorics. Prereq: MATH 2100, MATH 2350 or MATH 3100.

  • Lectures:
    M, W, F 9:00am - 9:50am
    Cudahy Hall 120
  • Office Hours:
    Monday, 1:00pm - 2:00pm
    in person, Cudahy 307
    Wednesday, 2:30pm - 3:30pm
    on Microsoft Teams
    and by appointment (just email me!)

Course Information

The official syllabus is available here.

 
Homework
Textbook

Important Dates
Tues, Jan 17 Classes begin
Wed, Jan 25 Last day to add/drop classes or request CR/NC option
Mon, Mar 6 — Sat, Mar 11 Midterm exam period
Mon, Mar 13 — Fri, Mar 17 Spring break, no classes
Thurs, Apr 6 — Mon, Apr 10 Easter break, no classes
Fri, Apr 14 Last day to withdraw from classes
Fri, May 5 Last day of classes

Daily Calendar
# Date Topics Announcements / Homework
Week 1
1 Wed, Jan 18 Syllabus
Topic 1 - Preliminaries (started)
2 Fri, Jan 20 Topic 1 - Preliminaries (finished)
Topic 2 - Strings and Languages (started)
Week 2
3 Mon, Jan 23 Topic 2 - Strings and Languages (finished)
Topic 3 - Regular Expressions (started)
XKCD #208
XKCD #1171
4 Wed, Jan 25 Topic 3 - Regular Expressions (continued)
5 Fri, Jan 27 Topic 3 - Regular Expressions (continued)
Week 3
6 Mon, Jan 30 Topic 3 - Regular Expressions (finished)
Topic 4 - Finite State Automata (started)
7 Wed, Feb 1 Homework 1 Assigned
Topic 4 - Finite State Automata (continued)
8 Fri, Feb 3 Topic 4 - Finite State Automata (continued)
Week 4
9 Mon, Feb 6 Topic 4 - Finite State Automata (continued)
10 Wed, Feb 8 Topic 4 - Finite State Automata (finished)
Topic 5 - Nondeterministic Finite Automata (started)
11 Fri, Feb 10 Homework 1 Due
Homework 2 Assigned
Topic 5 - Nondeterministic Finite Automata (continued)
Week 5
12 Mon, Feb 13 Topic 5 - Nondeterministic Finite Automata (continued)
13 Wed, Feb 15 Topic 5 - Nondeterministic Finite Automata (continued)
14 Fri, Feb 17 Topic 5 - Nondeterministic Finite Automata (basically finished)
Week 6
15 Mon, Feb 20 Topic 5 - Nondeterministic Finite Automata (basically finished)
Topic 6 - Regular vs. Recognizable Languages (started)
16 Wed, Feb 22 Class Cancelled Today
17 Fri, Feb 24 Homework 2 Due
Topic 6 - Regular vs. Recognizable Languages (continued)
Week 7
18 Mon, Feb 27 Homework 3 Assigned
Topic 6 - Regular vs. Recognizable Languages (finished)
19 Wed, Mar 1 Topic 7 - Nonregular Languages (started)
20 Fri, Mar 3 Topic 7 - Nonregular Languages (continued)
Week 8
21 Mon, Mar 6 Topic 7 - Nonregular Languages (continued)
22 Wed, Mar 8 Topic 7 - Nonregular Languages (finished)
Topic 8 - Applications of Regular Languages (started)
assorted links
23 Fri, Mar 10 Homework 3 Due
Topic 8 - Applications of Regular Languages (continued)
Spring Break
Mon, Mar 13 Spring Break — no classes
Wed, Mar 15 Spring Break — no classes
Fri, Mar 17 Spring Break — no classes
Week 9
24 Mon, Mar 20 Homework 4 Assigned
Final Project Assigned and Discusssed
(see pdf at top of page under Homework)
Topic 8 - Applications of Regular Languages (continued)
25 Wed, Mar 22 Topic 8 - Applications of Regular Languages (continued)
26 Fri, Mar 24 Topic 8 - Applications of Regular Languages (continued)
Week 10
27 Mon, Mar 27 Topic 8 - Applications of Regular Languages (continued)
28 Wed, Mar 29 Topic 8 - Applications of Regular Languages (finished)
29 Fri, Mar 31 Homework 4 Due
Topic 9 - Context-Free Grammars (started)
Week 11
30 Mon, Apr 3 Homework 4 Due
Final Project Progress — paper selection or one-page report
Topic 9 - Context-Free Grammars (continued)
31 Wed, Apr 5 Topic 9 - Context-Free Grammars (continued)
Fri, Apr 7 Easter Break – no classes
Week 12
Mon, Apr 10 Easter Break – no classes
32 Wed, Apr 12 Topic 9 - Context-Free Grammars (finished)
33 Fri, Apr 14 Topic V1 - The Myhill-Nerode Lemma (started)
Pre-recorded Video
Week 13
34 Mon, Apr 17 Topic V1 - The Myhill-Nerode Lemma (finished)
Pre-recorded Video
35 Wed, Apr 19 Topic V2 - DFA Minimization
Pre-recorded Video
Homework 5 Assigned
36 Fri, Apr 21 Topic 10 - Pushdown Automata (started)
Week 14
37 Mon, Apr 24 Topic 10 - Pushdown Automata (finished)
38 Wed, Apr 26 Presentations — NN, DR
39 Fri, Apr 28 Presentations — TM, ER
Week 15
40 Mon, May 1 Presentations — DC, TC
41 Wed, May 3 Presentations — AG, BB, MI
42 Fri, May 5 Homework 5 Due
Presentations — JN, AO