Homework and Programming Assignments




Note:
  1. Before solving the homework problems, you are expected to study and understand the related material.
  2. Homework assignments must be typed, saved as PDF, and electronically submitted on the Blackboard.
  3. It is highly recommeneded to do the homeowk in Latex. Please register with ShareLatex for an online account. Collaboration is only allowed in ShareLatex (must be shared with instructor before start).
  4. The homework PDF file must have a header on the first page, and a header for each question. See HW-format. You should follow this format when you submit your homework in order to be graded. See also a HW_Sample which can be used as a template for your homework.
  5. Assignments deadlines are announced on the Blackboard.
  6. Late submission is subjected to a 50% penalty if it is submitted by the cut-off time (usually 48 hours after the announced deadline).
  7. You may find your Class-SN here.

Homework problems are taken from Linz (online version) by default unless otherwise stated

Homework 1:
LNTC-Sec 1, Exer: 1, 2, 3, 4, 5, 6.
LNTC-Sec 2, Exer: 1, 2, 3, 4.
LNTC-Sec 3, Exer: 1(b, c, e, g, h, j), 2.
Linz-Sec 2.1, Exer: 7(c), 8(a).
Total: 14 exercises.

Homework 2:
LNTC - Sec 4, Exer: 1, 4.
Linz - Sec 1.2, Exer: 14(b, c, e, f, h), 15(a, d), 18(b).
Linz - Sec 2.2, Exer: 10.
Linz - Sec 2.3, Exer: 3*, 5, 6, 12.
Linz - Sec 3.1, Exer: 17(b, f), 20(and give a counterexample if not equivalent).
Linz - Sec 3.3, Exer: 6, 13(b).
(*Apply the NFA-to-DFA procedure as explained in class)
Total: 14 exercises.

Homework 3:
Linz - Sec 3.2, Exer: 1*, 9.
Linz - Sec 4.1, Exer: 8, 13, 17.
Linz - Sec 4.2, Exer: 3, 6, 11, 15.
Linz - Sec 4.3, Exer: 4(b, c, f), 10, 15(e, f, g), 16(and prove your answer), 24, 26.
(*Apply the procedure as explained in class)
Total: 15 exercises.

Homework 4:
Linz - Sec 5.1, Exer: 3, 7(a, c, e), 22, 24.
Linz - Sec 5.2, Exer: 7, 12, 13.
Linz - Sec 7.1, Exer: 3(c), 4(d, k).
Linz - Sec 7.2, Exer: 1, 9, 15.
Linz - Sec 7.3, Exer: 1, 3*, 18*.
(*Justify your answer)
Total: 15 exercises.

Homework 5:
Linz - Sec 6.1, Exer: 6, 7, 8, 15.
Linz - Sec 6.2, Exer: 2, 10.
Linz - Sec 6.3, Exer: 1, 2.
Linz - Sec 8.1, Exer: 3, 7(a).
Linz - Sec 8.2, Exer: 7, 16, 17, 23.
Total: 14 exercises.

Homework 6:
Linz - Sec 9.1, Exer: 2, 3, 4, 5, 7(d).
Linz - Sec 9.2, Exer: 3(b), 5, 9.
Linz - Sec 9.3, Exer: 2.
Linz - Sec 11.3, Exer: 1(a,b), 3.
Linz - Sec 11.4, Exer: 1.
Linz - Sec 12.1, Exer: 1, 10.
Total: 14 exercises.