**CSC 4170: Homework Assignments **

**Policy:** Homework will
not be graded. Using somebody's help when doing homework is not forbidden.
However, the quiz and examination questions will mostly come from the homework
assignments. Books or notes will not be allowed during a quiz or examination.

**Homework 1
**

**Next quiz **on September 11.

**Material covered:
**Slides 0.a - 1.2.m

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

Exercise 0.1 [Note: "N" stands for natural numbers. See page 4]

Exercise 0.2

Exercise 0.3

Exercise 0.4

Exercise 0.5

Exercise 1.2

Exercise 1.3

Exercise 1.4

Exercise 1.5(a,b,c,g,h)

Exercise 1.6(a,b,d,e,g,i,k,m,n)

Exercise 1.7(a,b,c,d,g)

Exercise 1.16

**Homework 2
**

**Next quiz **on September 25.

**Material covered:
**Slides 1.3.a - 1.4.e

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

- Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
- Exercise 1.20
- Exercise 1.19
- Exercise 1.21
- Exercise 1.27
- Make
sure you understand the formulation (statement) of the pumping lemma and
can accurately reproduce it. No proof of this lemma is required though.

- Using
the pumping lemma, prove that the language
**{0**≥^{n}1^{n}| n**0}**is not regular.

- Using
the pumping lemma, prove that the language
**{ww | w**∈**{0,1}**is not regular.^{*}} - Using
the pumping lemma, prove that the language
**{0**is not regular.^{m}1^{n}| 0<m<n} - Using
the pumping lemma, prove that the language
**{0**is not regular (hint: think of^{m}1^{n}| 0<n<m}*pumping out*instead of pumping in).