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
10 Wed, Feb 8
11 Fri, Feb 10 Homework 1 Due
Week 5
12 Mon, Feb 13
13 Wed, Feb 15
14 Fri, Feb 17
Week 6
15 Mon, Feb 20
16 Wed, Feb 22
17 Fri, Feb 24
Week 7
18 Mon, Feb 27
19 Wed, Mar 1
20 Fri, Mar 3
Week 8
21 Mon, Mar 6
22 Wed, Mar 8
23 Fri, Mar 10
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
25 Wed, Mar 22
26 Fri, Mar 24
Week 10
27 Mon, Mar 27
28 Wed, Mar 29
29 Fri, Mar 31
Week 11
30 Mon, Apr 3
31 Wed, Apr 5
Fri, Apr 7 Easter Break – no classes
Week 12
Mon, Apr 10 Easter Break – no classes
32 Wed, Apr 12
33 Fri, Apr 14
Week 13
34 Mon, Apr 17
35 Wed, Apr 19
36 Fri, Apr 21
Week 14
37 Mon, Apr 24
38 Wed, Apr 26
39 Fri, Apr 28
Week 15
40 Mon, May 1
41 Wed, May 3
42 Fri, May 5