2019 Fall  304  Foundations of Computer Science  Syllabus
1 Important Course Details
2 Schedule
Day 
 Date 
 Topic 
 Notes  
1 
 Thu 
 09/05 
 Preliminaries 


2 
 Tue 
 09/10 
 Finite Automata 


3 
 Thu 
 09/12 
 (cont.) 


4 
 Tue 
 09/17 
 (cont.) 


5 
 Thu 
 09/19 
 NonDeterministic Finite Automata 


6 
 Tue 
 09/24 
 (cont.) 


7 
 Thu 
 09/26 
 (cont.) 


8 
 Tue 
 10/01 
 Regular Expressions 


9 
 Thu 
 10/03 
 (cont.) 


10 
 Tue 
 10/08 
 NonRegular Languages 


11 
 Thu 
 10/10 
 (cont.) 


 Tue 
 10/15 
 No class  
12 
 Thu 
 10/17 
 ContextFree Grammars 


13 
 Tue 
 10/22 
 Pushdown Automata 


14 
 Thu 
 10/24 
 (cont.) 


15 
 Tue 
 10/29 
 (cont.) 


16 
 Thu 
 10/31 
 NonContextFree Languages 


17 
 Tue 
 11/05 
 (cont.) 


18 
 Thu 
 11/07 
 Turing Machines 


19 
 Tue 
 11/12 
 (cont.) 


20 
 Thu 
 11/14 
 Variants of Turing Machines 


21 
 Tue 
 11/19 
 (cont.) 


22 
 Thu 
 11/21 
 ChurchTuring Thesis 


23 
 Tue 
 11/26 
 Decidable Languages 


 Thu 
 11/28 
 No class  
24 
 Tue 
 12/03 
 (cont.) 


25 
 Thu 
 12/05 
 Halting Problems 


26 
 Tue 
 12/10 
 (cont.) 


27 
 Thu 
 12/12 
 Reducibility 


3 Work in this Course
3.1 Checkpoints
3.1.1 Checkpoint #1
Prepare a presentation (see Presentation Policy for how to submit) that presents an argument for which tasks you completed in your project. If this argument is not wellformulated, or if you present work that is not your own, then you will get an F on the assignment.
3.1.2 Checkpoint #2
Prepare a presentation (see Presentation Policy for how to submit) that presents an argument for which tasks you completed in your project. If this argument is not wellformulated, or if you present work that is not your own, then you will get an F on the assignment.
3.2 Course Grade
Your course grade is based on how many tasks you complete in the course project on the second checkpoint. However, this grade is modified by two things: first, if you are a graduate student or HonorsbyContract student, then you are expected to do more, so it will be reduced by one rank (i.e., A becomes B, S becomes A, and so on.); second, if you did not achieve a grade with the letter C in it on the first checkpoint, then your grade is also reduced by one rank.
3.3 Course Project
Your main project in this course is to build a library of simulators and analyses for the models of computation discussed in lecture (and in the textbook.) This library will constitute a set of constructive proofs of the theorems discussed in the course.
There is a lot of flexibility about how you do this; in particular, you can implement it in whatever language you want. Lectures typically describe either data structures (like the models themselves) or algorithms. In both cases, we will not often explicitly discuss how to program them, because the details are more about your implementation language than the core content discussed.

 Grade 
 Time 
 Lines  
1 
 Decide on a data type to represent alphabets and characters. 
 F 
 1m (0.15%) (1h) 
 +10 / 0 (0.40%) (10) 
2 
 Decide on a data type to represent strings. 
 F 
 1m (0.15%) (1h) 
 +5 / 2 (0.52%) (13) 
3 
 Write a function that generates the Nth string of a given alphabet’s lexicographic order. 
 F 
 13m (1.95%) (1h) 
 +57 / 4 (2.63%) (66) 
4 
 Define a data type to represent DFAs. 
 F 
 1m (0.15%) (1h) 
 +8 / 1 (2.91%) (73) 
5 
 Write the definition of a DFA that accepts no strings. 
 F 
 2m (0.30%) (1h) 
 +14 / 1 (3.43%) (86) 
6 
 Write the definition of a DFA that accepts only the empty string. 
 F 
 1m (0.15%) (1h) 
 +10 / 1 (3.78%) (95) 
7 
 Write a function that when given a character returns a DFA that accepts only strings of exactly that character. 
 F 
 3m (0.45%) (1h) 
 +21 / 6 (4.38%) (110) 
8 
 Write a dozen example DFAs. 
 F 
 7m (1.05%) (1h) 
 +56 / 11 (6.18%) (155) 
9 
 For each example DFA, write a dozen tests of their behavior. 
 F 
 5m (0.75%) (1h) 
 +38 / 2 (7.61%) (191) 
10 
 Write a function that given a DFA and a string, determines if the string is accepted. 
 F 
 5m (0.75%) (1h) 
 +36 / 18 (8.33%) (209) 
11 
 Write a function that given a DFA and a string, returns the trace of configurations it visits. 
 F 
 3m (0.45%) (1h) 
 +24 / 5 (9.08%) (228) 
12 
 Write a function that given a DFA, returns a string that would be accepted (or false if this is not possible). 
 F 
 9m (1.35%) (1h) 
 +50 / 21 (10.24%) (257) 
13 
 (Complement) Write a function that takes one DFA and returns a DFA that accepts that the given one does not (and vice versa). 
 F 
 1m (0.15%) (1h) 
 +12 / 2 (10.64%) (267) 
14 
 (Union) Write a function that takes two DFAs and returns a third DFA that accepts a string if either argument accepts it. 
 F 
 2m (0.30%) (1h) 
 +20 / 1 (11.39%) (286) 
15 
 Write a dozen tests for your union function. 
 F 
 1m (0.15%) (1h) 
 +8 / 1 (11.67%) (293) 
16 
 (Intersect) Write a function that takes two DFAs and returns a third DFA that accepts a string if both arguments accepts it. 
 F 
 1m (0.15%) (1h) 
 +13 / 5 (11.99%) (301) 
17 
 Write a dozen tests for your intersection function. 
 F 
 1m (0.15%) (1h) 
 +10 / 3 (12.27%) (308) 
18 
 (Subset) Write a function which takes two DFAs (X and Y) and returns whether every string accepted by X is also accepted by Y. 
 F 
 2m (0.30%) (1h) 
 +21 / 2 (13.03%) (327) 
19 
 Write a dozen tests for your subset function. 
 F 
 1m (0.15%) (1h) 
 +7 / 4 (13.15%) (330) 
20 
 (Equality) Write a function which takes two DFAs (X and Y) and returns whether every string accepted by X is also accepted by Y and vice versa. 
 F 
 1m (0.15%) (2h) 
 +8 / 1 (13.43%) (337) 
21 
 Write a dozen tests for your equality function. 
 F 
 2m (0.30%) (2h) 
 +13 / 2 (13.86%) (348) 
22 
 Verify your complement, union, and intersect functions using the equality function. 
 F 
 2m (0.30%) (2h) 
 +21 / 2 (14.62%) (367) 
23 
 Define a data type to represent NFAs. 
 F 
 1m (0.15%) (2h) 
 +15 / 1 (15.18%) (381) 
24 
 Write a (trivial) function that converts DFAs into NFAs. 
 F+ 
 1m (0.15%) (2h) 
 +11 / 1 (15.58%) (391) 
25 
 Write a dozen example NFAs. 
 F+ 
 4m (0.60%) (2h) 
 +34 / 17 (16.25%) (408) 
26 
 For each example NFA, write a dozen traces of their behavior. 
 F+ 
 4m (0.60%) (2h) 
 +18 / 2 (16.89%) (424) 
27 
 (Oracle) Write a function that given an NFA, a string, a trace, and a boolean, determines if the trace is a valid execution of the NFA and accepts results in the given boolean. 
 F+ 
 9m (1.35%) (2h) 
 +29 / 13 (17.53%) (440) 
28 
 Define a data type to represent trace trees. 
 F+ 
 1m (0.15%) (2h) 
 +9 / 1 (17.85%) (448) 
29 
 For each example NFA, write a halfdozen trace trees of their behavior. 
 F+ 
 9m (1.35%) (2h) 
 +24 / 6 (18.57%) (466) 
30 
 (Forking) Write a function that given an NFA and a string, returns a tree of all possible traces. 
 F+ 
 13m (1.95%) (2h) 
 +36 / 2 (19.92%) (500) 
31 
 For each example NFA, write a dozen tests of their behavior. 
 F+ 
 3m (0.45%) (2h) 
 +21 / 3 (20.64%) (518) 
32 
 (Backtracking) Write a function that given an NFA and a string, determines if the string is accepted. 
 F+ 
 2m (0.30%) (2h) 
 +14 / 1 (21.16%) (531) 
33 
 (Union) Write a function that takes two NFAs and returns a third NFA that accepts a string if either argument accepts it. 
 F+ 
 11m (1.65%) (3h) 
 +92 / 20 (24.02%) (603) 
34 
 (Concatenation) Write a function that takes two NFAs and returns a third NFA that accepts a string if it can be broken into two pieces, one accepted by the first NFA and the other accepted by the second. 
 F+ 
 2m (0.30%) (3h) 
 +29 / 2 (25.10%) (630) 
35 
 Write a dozen tests for your concatenation function. 
 F+ 
 1m (0.15%) (3h) 
 +10 / 2 (25.42%) (638) 
36 
 (Kleene Star) Write a function that takes an NFA and returns a new NFA that accepts a string if it can be broken into N pieces, each accepted by the argument. 
 F+ 
 1m (0.15%) (3h) 
 +22 / 1 (26.25%) (659) 
37 
 Write a dozen tests for your Kleene star function. 
 F+ 
 14m (2.10%) (3h) 
 +45 / 17 (27.37%) (687) 
38 
 Write a function which converts an NFA into a DFA that accepts the same language. 
 F+ 
 3m (0.45%) (3h) 
 +32 / 1 (28.61%) (718) 
39 
 Ensure that all of your NFA tests return the correct results when converted to DFAs and run through the DFA accept function. 
 F+ 
 1m (0.15%) (3h) 
 +8 / 3 (28.80%) (723) 
40 
 Manually convert a few NFAs to DFAs and verify the output of your compiler with your DFA equality function. 
 F+ 
 5m (0.75%) (3h) 
 +37 / 1 (30.24%) (759) 
41 
 Define a data type to represent regular expressions. 
 D 
 4m (0.60%) (3h) 
 +15 / 1 (30.80%) (773) 
42 
 Write a printer for regular expressions. 
 D 
 4m (0.60%) (3h) 
 +15 / 2 (31.31%) (786) 
43 
 Write a dozen example regular expressions. 
 D 
 6m (0.90%) (3h) 
 +27 / 3 (32.27%) (810) 
44 
 For each regular expressions, write a few examples of accepted strings and rejected strings. 
 D 
 1m (0.15%) (3h) 
 +9 / 2 (32.55%) (817) 
45 
 (Generator) Write a function that accepts a regular expressions and generates a random string that would be accepted by it. 
 D 
 5m (0.75%) (3h) 
 +21 / 2 (33.31%) (836) 
46 
 Write a compiler from regular expressions to NFAs. 
 D 
 4m (0.60%) (3h) 
 +27 / 3 (34.26%) (860) 
47 
 Verify that your regular expression compiler works by using DFA equality testing in a few ways. 
 D 
 1m (0.15%) (3h) 
 +7 / 2 (34.46%) (865) 
48 
 Write an equality checker for regular expressions. 
 D 
 1m (0.15%) (3h) 
 +9 / 1 (34.78%) (873) 
49 
 Write a dozen tests for your regular expression equality checker. 
 D+ 
 1m (0.15%) (3h) 
 +7 / 2 (34.98%) (878) 
50 
 Write an optimizer for regular expressions that simplifies them. 
 D+ 
 9m (1.35%) (4h) 
 +41 / 2 (36.53%) (917) 
51 
 Define a data type to represent GNFAs. 
 D+ 
 1m (0.15%) (4h) 
 +7 / 1 (36.77%) (923) 
52 
 Write a function that converts DFAs into equivalent regular expressions. 
 D+ 
 18m (2.69%) (4h) 
 +78 / 12 (39.40%) (989) 
53 
 Verify that your ripper works by checking that the generator always produces strings accepted by the DFA. 
 D+ 
 16m (2.40%) (4h) 
 +5 / 1 (39.56%) (993) 
54 
 Verify that your ripper works by checking that the DFA is equal to the DFA produced by compiling the regular expression derived from it. 
 D+ 
 16m (2.40%) (4h) 
 +7 / 1 (39.80%) (999) 
55 
 Write a dozen examples of the regular pumping property holding true on your example machines. 
 C 
 7m (1.05%) (5h) 
 +31 / 1 (41.00%) (1029) 
56 
 (Pumper) Write a function which given a DFA, a string, and an accepting trace returns three substrings (x, y, and z) that satisfy the clauses of the regular pumping lemma, if the input string is long enough. 
 C 
 23m (3.44%) (5h) 
 +41 / 9 (42.27%) (1061) 
57 
 (RePumper) Write a function which given three strings that satisfy the conclusion of the pumping lemma constructs a DFA. 
 C 
 5m (0.75%) (5h) 
 +52 / 27 (43.27%) (1086) 
58 
 Verify that your pumper works by showing that your repumper’s result is always a subset of the original DFA. 
 C 
 1m (0.15%) (5h) 
 +6 / 2 (43.43%) (1090) 
59 
 Define a data type to represent contextfree grammars. 
 C 
 1m (0.15%) (5h) 
 +16 / 2 (43.98%) (1104) 
60 
 Define a data type to represent CFG parse trees. 
 C 
 2m (0.30%) (5h) 
 +9 / 2 (44.26%) (1111) 
61 
 Write a dozen example contextfree grammars. 
 C 
 7m (1.05%) (5h) 
 +32 / 1 (45.50%) (1142) 
62 
 For each contextfree grammar, write a few examples of generated strings and strings that are not generated. 
 C 
 3m (0.45%) (5h) 
 +23 / 4 (46.25%) (1161) 
63 
 Write a function that accepts a CFG and returns a random string derived from the grammar along with its parse tree. 
 C 
 11m (1.65%) (5h) 
 +44 / 9 (47.65%) (1196) 
64 
 (Generator) Write a function that accepts a CFG and a number N, and returns all strings generated by it where the derivation tree is less than N levels deep. 
 C 
 11m (1.65%) (6h) 
 +31 / 2 (48.80%) (1225) 
65 
 Write a function that converts a DFA into a CFG. 
 C 
 12m (1.80%) (6h) 
 +40 / 16 (49.76%) (1249) 
66 
 Write a function that accepts a CFG and a parse tree and returns whether the parse tree obeys the rules of the CFG. 
 C 
 7m (1.05%) (6h) 
 +29 / 3 (50.80%) (1275) 
67 
 Write a function that accepts a CFG and returns whether it is Chomsky Normal Form. 
 C 
 13m (1.95%) (6h) 
 +65 / 23 (52.47%) (1317) 
68 
 Write a function that accepts a CFG and converts it into Chomsky Normal Form. 
 C 
 54m (8.08%) (7h) 
 +127 / 3 (57.41%) (1441) 
69 
 Define a data type to represent pushdown automata. 
 C+ 
 1m (0.15%) (7h) 
 +16 / 1 (58.01%) (1456) 
70 
 Write a dozen example PDAs. 
 C+ 
 6m (0.90%) (7h) 
 +23 / 1 (58.88%) (1478) 
71 
 For each PDA, write a halfdozen examples of accepted and rejected strings. 
 C+ 
 1m (0.15%) (7h) 
 +13 / 1 (59.36%) (1490) 
72 
 Write an oraclestyle PDA interpreter, like you did for NFAs. 
 C+ 
 12m (1.80%) (7h) 
 +37 / 4 (60.68%) (1523) 
73 
 Write a forkingstyle PDA interpreter, like you did for NFAs. 
 C+ 
 11m (1.65%) (8h) 
 +47 / 5 (62.35%) (1565) 
74 
 Write a backtrackingstyle PDA interpreter, like you did for NFAs. 
 C+ 
 6m (0.90%) (8h) 
 +47 / 10 (63.82%) (1602) 
75 
 Write a function that converts a CFG into an equivalent PDA. 
 C+ 
 39m (5.84%) (8h) 
 +93 / 31 (66.29%) (1664) 
76 
 Write a halfdozen examples of the context free pumping property holding on your example CFGs. 
 C+ 
 3m (0.45%) (8h) 
 +20 / 1 (67.05%) (1683) 
77 
 (Pumper) Write a function that accepts a CFG and a parse tree and returns the substrings that satisfy the conclusion of the contextfree pumping property, if the output string is long enough. 
 C+ 
 27m (4.04%) (9h) 
 +69 / 5 (69.60%) (1747) 
78 
 (RePumper) Write a function that accepts the substrings of the CFPP for a CFG and generates a CFG. 
 C+ 
 9m (1.35%) (9h) 
 +32 / 11 (70.44%) (1768) 
79 
 Verify that your pumper works by showing that your repumper’s output generates strings accepted by a PDA corresponding to your original CFG. 
 C+ 
 1m (0.15%) (9h) 
 +8 / 2 (70.68%) (1774) 
80 
 Define a data type to represent Turing machine tapes. 
 B 
 4m (0.60%) (9h) 
 +40 / 2 (72.19%) (1812) 
81 
 Define a data type to representing Turing machines. 
 B 
 2m (0.30%) (9h) 
 +18 / 1 (72.87%) (1829) 
82 
 Encode the example Turing machines from the book and from class. 
 B 
 17m (2.54%) (9h) 
 +68 / 18 (74.86%) (1879) 
83 
 Write a dozen examples, per machine, of strings, some accepted and some rejected. 
 B 
 3m (0.45%) (9h) 
 +26 / 3 (75.78%) (1902) 
84 
 For each machine, write out a trace of the execution of the machine on a nontrivial string. 
 B 
 2m (0.30%) (9h) 
 +18 / 1 (76.45%) (1919) 
85 
 Write a function that simulates a Turing machine and returns a list of the configurations it visited. 
 B 
 3m (0.45%) (10h) 
 +18 / 5 (76.97%) (1932) 
86 
 Write a function that simulates a Turing machine running on some input. 
 B 
 10m (1.50%) (10h) 
 +52 / 4 (78.88%) (1980) 
87 
 Write a function that converts a DFA into a Turing machine. 
 B+ 
 3m (0.45%) (10h) 
 +28 / 10 (79.60%) (1998) 
88 
 Write a function that simulates a Turing machine and returns the tape contents ahead of it when it accepts. 
 B+ 
 1m (0.15%) (10h) 
 +12 / 1 (80.04%) (2009) 
89 
 Implement and test a computable function that increments a binary number. 
 B+ 
 5m (0.75%) (10h) 
 +30 / 2 (81.16%) (2037) 
90 
 Implement and test a computable function that decrements a binary number. 
 B+ 
 4m (0.60%) (10h) 
 +22 / 1 (81.99%) (2058) 
91 
 Implement and test a computable function that adds two arbitrarybit binary numbers separated by the + symbol. 
 B+ 
 10m (1.50%) (10h) 
 +62 / 13 (83.94%) (2107) 
92 
 Define a data type to represent stayput Turing machines. 
 B+ 
 0m (0.00%) (10h) 
 +7 / 1 (84.18%) (2113) 
93 
 Write a couple example stayput Turing machines. 
 A 
 2m (0.30%) (10h) 
 +19 / 1 (84.90%) (2131) 
94 
 Write a function that converts stayput Turing machines into normal Turing machines. 
 A 
 6m (0.90%) (10h) 
 +29 / 6 (85.82%) (2154) 
95 
 Define a data type to represent multitape Turing machines. 
 A 
 3m (0.45%) (10h) 
 +13 / 1 (86.29%) (2166) 
96 
 Write a simulator for multitape Turing machines. 
 A 
 4m (0.60%) (10h) 
 +23 / 3 (87.09%) (2186) 
97 
 (Union) Write a function that takes two Turing machines and returns a 2tape Turing machine that accepts the union of the two machines’ languages. 
 A+ 
 19m (2.84%) (11h) 
 +73 / 5 (89.80%) (2254) 
98 
 (Intersect) Write a function that takes two Turing machines and returns a 2tape Turing machine that accepts the intersection of the two machines’ languages. 
 A+ 
 4m (0.60%) (11h) 
 +17 / 3 (90.36%) (2268) 
99 
 Write a computable functionstyle simulator for multitape Turing machines. 
 A+ 
 2m (0.30%) (11h) 
 +9 / 1 (90.68%) (2276) 
100 
 Implement and test a twotape computable function that adds two arbitrarybit binary numbers separated by the + symbol. 
 A+ 
 23m (3.44%) (11h) 
 +94 / 6 (94.18%) (2364) 
101 
 Define a data type to represent polynomials over a single variable. 
 S+ 
 1m (0.15%) (11h) 
 +18 / 8 (94.58%) (2374) 
102 
 Write a dozen example polynomials. 
 SS 
 3m (0.45%) (11h) 
 +14 / 1 (95.10%) (2387) 
103 
 For a few of the example polynomials, figure out their roots. 
 SS 
 5m (0.75%) (11h) 
 +29 / 2 (96.18%) (2414) 
104 
 Write a function which given a polynomial determines its integral roots, if it has any. 
 SS 
 6m (0.90%) (11h) 
 +41 / 19 (97.05%) (2436) 
105 
 Implement and test an integer pairing function. 
 SS 
 2m (0.30%) (11h) 
 +19 / 1 (97.77%) (2454) 
106 
 Implement an integer unpairing function. 
 SS 
 3m (0.45%) (11h) 
 +14 / 2 (98.25%) (2466) 
107 
 Implement and test a Karity integer pairing function. 
 SS 
 2m (0.30%) (11h) 
 +17 / 1 (98.88%) (2482) 
108 
 Implement a Karity integer unpairing function. 
 SS 
 5m (0.75%) (12h) 
 +13 / 2 (99.32%) (2493) 
109 
 Implement a function that accepts a sequence of real numbers and returns a real number that is not in the sequence. 
 SS 
 4m (0.60%) (12h) 
 +19 / 2 (100.00%) (2510) 
110 
 Write a function that accepts a CFG and returns whether it describes the empty language. 
 SS 

 
111 
 Implement a function that encodes Turing machine description as integers. 
 SS 

 
112 
 Implement a function that decodes Turing machines as encoded integers. 
 SS+ 

 
113 
 Implement a function that mimics the Halting Problem proof. 
 SS+ 

 
114 
 Write a function that converts a PDA into an equivalent CFG. 
 SS+ 

 
115 
 Define a data type to represent nondeterministic Turing machines. 
 SS+ 

 
116 
 Write a few trivial example nondeterministic Turing machines. 
 SS+ 

 
117 
 Write an oraclestyle NTM interpreter. 
 SS+ 

 
118 
 Write a backtrackingstyle NTM interpreter. 
 SS+ 

 
119 
 (Concatenation) Write a function that takes two Turing machines and returns a nondeterministic Turing machine that accepts the concatenation of the two machines’ languages. 
 SS+ 

