CS622: Theory of Formal Languages
UMass Boston, Spring 2024
Mon, 15 Jan 2024 00:00:00 -0500
Hi Students,
Welcome to CS622! I am looking forward to the semester.
To ensure a smooth start, please fill out this pre-class survey as soon as you can. (Enter your full umb.edu email into the Google sign-in box to access the survey. You may need to sign out of other accounts first, or open the link in an incognito window.) This way I can address any concerns as soon as possible.
Also, please note that this is a math course, and discrete math is a pre-requirement (so you’ll want to brush up if it’s been a while).
See you in the first class!
Last updated: Mon, 22 Apr 2024 11:45:14 -0400
Schedule (subject to change):
Lectures meet MWF 1:00-1:50pm in McCormack M02-0423
Readings: S = Sipser; HMU = Hopcroft, Motwani, Ullmann
# | Date | Topic | Reading | HW out |
1 | 1/22 Mon | Welcome to CS622 [slides] | S0.2-0.4, HMU1.2-1.4 | |
2 | 1/24 Wed | Intro to Proofs [slides] | S0.2-0.4, HMU1.2-1.4 | |
3 | 1/26 Fri | CS622 Logistics [slides] | S0.2-0.4, HMU1.2-1.4 | |
4 | 1/29 Mon | Using and Proving Logical Statements [slides] | HMU1.2-1.4 | |
5 | 1/31 Wed | Deterministic Finite Automata (DFA) [slides] | S1.1 | |
6 | 2/2 Fri | Computing with DFAs [slides] | HMU2.2 | |
7 | 2/5 Mon | Computing with DFAs, Formally [slides] | HMU2.2 | |
8 | 2/7 Wed | Regular Languages [slides] | S1.1, HMU2.2 | |
9 | 2/9 Fri | Proving a Language Regular [slides] | S1.1, HMU2.2 | |
10 | 2/12 Mon | Combining DFAs, Closed Ops [slides] | S1.1, HMU2.2 | |
11 | 2/14 Wed | Reg Langs Closed Under Union NFAs [slides] | S1.2, HMU2.3,2.5 | |
12 | 2/16 Fri | Nondeterminism and NFAs [slides] | S1.2, HMU2.3,2.5 | |
no class | 2/19 Mon | President’s Day | ||
13 | 2/21 Wed | Computing with NFAs [slides] | S1.2, HMU2.3,2.5 | |
14 | 2/23 Fri | Concat Closed [slides] | S1.2, HMU2.3 | |
15 | 2/26 Mon | NFA -> DFA [slides] | S1.2, HMU2.3 | |
16 | 2/28 Wed | Regular Expressions [slides] | S1.3 | |
17 | 3/1 Fri | GNFA->Reg Expression [slides] | S1.3 | |
18 | 3/4 Mon | Proof by Induction [slides] | S0.4,1.3, HMU1.4 | |
19 | 3/6 Wed | Non-Regular Languages [slides] | S1.4 | |
20 | 3/8 Fri | Proving Languages Non-Regular [slides] | S1.4 | |
no class | 3/11 Mon | Spring Break | ||
no class | 3/13 Wed | Spring Break | ||
no class | 3/15 Fri | Spring Break | ||
21 | 3/18 Mon | Context-free Grammars (CFG) [slides] | S2.1, HMU5.1 | |
22 | 3/20 Wed | Pushdown Automata (PDA) [slides] | S2.2, HMU6.1 | |
23 | 3/22 Fri | PDA Computation [slides] | S2.2, HMU6.1 | |
24 | 3/25 Mon | PDA<=>CFL, DPDAs [slides] | S2.2,2.4, HMU6.1 | |
25 | 3/27 Wed | non-CFLs [slides] | S2.3 | |
26 | 3/29 Fri | CFL Pumping Lemma, TM Intro [slides] | S3.1-3.3 | |
27 | 4/1 Mon | Turing Machines (TMs) [slides] | S3.1-3.3 | |
28 | 4/3 Wed | Multi-tape TMs, TM configs [slides] | S3.2 | |
29 | 4/5 Fri | Nondeterministic TMs [slides] | S3.2 | |
30 | 4/8 Mon | Decidability [slides] | S4.1 | |
31 | 4/10 Wed | Decidability for DFAs [slides] | S4.1 | |
32 | 4/12 Fri | Decidability for CFLs [slides] | S4.1 | |
no class | 4/15 Mon | Patriot’s Day | ||
33 | 4/17 Wed | Chomsky Normal Form [slides] | S2.1 | |
no class | 4/18 Thu | Course P/F/Withdraw Deadline | ||
34 | 4/19 Fri | Countability [slides] | S4.2 | |
35 | 4/22 Mon | Undecidability [slides] | S4.2,5.1, HMU9.3 | |
36 | 4/24 Wed | Reducibility [slides] | S4.2,5.1, HMU9.3 | |
37 | 4/26 Fri | Reducibility - Modify TM [slides] | S5.1, HMU9.3 | |
38 | 4/29 Mon | Mapping Reducibility | S5.3, HMU9.5 | |
39 | 5/1 Wed | Unrecognizability | S4.2,5.2-5.3, HMU9.5 | 11 |
40 | 5/3 Fri | Intro to Time Complexity | S7.1 | |
41 | 5/6 Mon | P | S7.2-3 | |
42 | 5/8 Wed | NP | S7.2-3 | 12 |
no class | 5/10 Fri | Study Period | ||
no class | 5/13 Mon | Final Exam Period | ||
no class | 5/15 Wed | Final Exam Period | ||
no class | 5/17 Fri | Final Exam Period |