CS:4330:0001 Theory of Computation, Fall 2020
3:30-4:45pm, Zoom from ICON
You may make an appointment to see us outside of the regular office hours.
Syllabus,
Announcements,
Homeworks,
Quizzes,
Exams,
Lecture Notes,
-
Welcome to the class! This web site is the place where you will see
homework assignments and lecture notes. The assignments on ICON will
refer to this page.
Every submission will on ICON before the midnight of the due day.
Only a single word file or pdf file is accepted. If you use pictures,
please insert all pictures into a word file. Other types of files are
ignored.
Please start each question with the number of the question.
There are 10 homeworks, each counts for 4% of the final grade.
- Homework 1 (40 points) Due date: 9/2/20
Page 26-27: 0.7, 0.11;
Page 83-84: 1.4 (a, c, e, f, g); 1.5 (c-g); 1.6 (a-e).
sample solutions
- Homework 2 (40 points) Due date: 9/9/20
Page 84-86: 1.10; 1.12, 1.13; 1.16; 1.17; 1.19; 1.21.
sample solutions
- Homework 3 (40 points) Due date: 9/16/2020
Page 86-90: 1.28; 1.29(b); 1.32; 1.34; 1.41; 1.42; 1.46 (a, c); 1.47.
sample solutions
- Homework 4 (40 points) Due date: 9/23/2020
Page 154-157: 2.4 (b,c,e; for b and c, provide both a right-linear and a left-linear CFG);
2.6 (b,d); 2.9; 2.14; 2.16; and the following problem.
Show the table filled by the CYK algorithm with CFG G and the input
string w = ababa, where G = ({S, A, B, C}, {a, b}, P, S) and P is
S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a
and answer the question: Is ababa in L(G)?
sample solutions
- Homework 5 (40 points) Due date: 09/30/2020
Page 157-158: 2.12; 2.13; 2.25; 2.30 (d); 2.31; 2.32; 2.39; 2.44.
sample solutions
- Homework 6 (40 points) Due date: 10/14/2020
Page 188-189: 3.8 (b,c) (give details of how the head moves and the tape
is changed); 3.9; 3.11; 3.13; 3.15 (b,d); 3.16 (c,d).
sample solutions
- Homework 7 (40 points) Due date: 10/22/2020
Page 211-212: 4.3; 4.4; 4.8; 4.11; 4.13; 4.21; 4.24; 4.29.
sample solutions
and its supplements
- Homework 8 (40 points) Due date: 11/02/2020
Page 212: 4.31.
Page 239-240: 5.9; 5.12; 5.13; 5.30 (b,c) (No use of Rice's
Theorem in this homework).
sample solutions
- Homework 9 (40 points) Due date: 11/09/2020
Page 240-242: 5.17; 5.18; 5.22; 5.23; 5.32; 5.34; 5.35.
sample solutions
- Homework 10 (40 points) Due date: 11/19/2020
Page 322-324: 7.7; 7.10; 7.13; 7.15; 7.18; 7.21; 7.22; 7.24.
sample solutions
- Bonus Homework (40 points) Due date: 12/07/2020
Page 325-327: 7.26; 7.30; 7.31; 7.35; 7.38; 7.43.
sample solutions
As these lecture notes are updated after each class, please don't
download them all in advance.
Have a great day!