CIS 570/770
(Introduction to) Formal Language Theory
Spring 2023 Schedule

This schedule is subject to minor modifications along the way

General remarks


Schedule

Class     TopicLinz HomeworkExam
1: Tue
Jan 17
Introduction Sections 1.1-2
2: Thu
Jan 19
DFAs Section 2.1
3: Tue
Jan 24
NFAs Section 2.2
4: Thu
Jan 26
Manipulating FAs Sections 2.3-4 #1 due
over weekend
Tue
Jan 31
Class canceled
5: Thu
Feb 2
Regular Expressions Section 3.1 #2 due
over weekend
6: Tue
Feb 7
Conversions between
FAs and Regular Expressions
Section 3.2
7: Thu
Feb 9
Regular Languages Sections 4.1-2 (+ 3.3) #3 due
over weekend
8: Tue
Feb 14
Non-Regular Languages Sections 4.3
9: Thu
Feb 16
Wrap up (Non)Regular Languages #4 due
over weekend
10: Tue
Feb 21
Context-Free Grammars (CFGs) Sections 5.1&3
11: Thu
Feb 23
Examples of CFGs
Review session
12: Tue
Feb 28
Exam #1
13: Thu
Mar 2
Ambiguity of CFGs Section 5.2 #5 due
over weekend
14: Tue
Mar 7
Transformations on CFGs Sections 6.1-2
15: Thu
Mar 9
Wrap up CFGs Section 6.3 #6 due
over Spring break
16: Tue
Mar 21
Pushdown Automata (PDA) Section 7.1
17: Thu
Mar 23
Convert between PDAs and CFGs
Deterministic PDAs
Section 7.2
Section 7.3
#7 due
over weekend
18: Tue
Mar 28
Pumping Lemma for
Context-Free Languages (CFLs)
Section 8.1
19: Thu
Mar 30
Closure Properties of CFLs Section 8.2 #8 due
over weekend
20: Tue
Apr 4
Wrap up CFGs and CFLs
21: Thu
Apr 6
Compilers
LL parsing
Chapter 15
Chapter 16
22: Tue
Apr 11
Exam #2
23: Thu
Apr 13
Wrap up LL parsing
Motivate LR parsing
Chapter 16 #9 due
over weekend
24: Tue
Apr 18
LR parsing Chapter 17
summarized in uploaded notes
25: Thu
Apr 20
Turing MachinesChapter 9 #10 due
over weekend
26: Tue
Apr 25
TMs, Variations
Stack/Counter Machines
Section 10.1
27: Thu
Apr 27
MultiTape TMs
Nondeterministic TMs
Universal TM
Recursive/RE languages
Section 10.2
Section 10.3
Section 10.4
Section 11.1
#11 due
over weekend
28: Tue
May 2
Undecidability (770 only) Chapter 12
29: Thu
May 4
Review session
Mon
May 8
Final Exam
2:00--3:50pm