**CSC 4170:
Homework Assignments **

**Policy:**
Homework will not be graded. Using somebody's help when doing homework is not
forbidden. However, the quiz problems will usually come from the homework
assignments (one question from the latest two assignments, and one from an
earlier assignment). Books or notes will not be allowed during the quiz.

**September
2**

**Material covered:
**Slides 0.a - 1.1.b

**Assignment:**

·
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.1

**September
4**

**Material covered:
**Slides 1.1.c - 1.2.b

**Assignment:**

·
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)

**September
9**

**Material covered:
**Slides 1.2.c - 1.2.m

**Assignment:**

·
Exercise
1.16

**September
11**

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

**Assignment:**

·
Exercise
1.18 (a,b,c,d,e,g,k,l,m,n)

·
Exercise
1.20

**September
16**

**Material covered:
**Slides 1.3.f - 1.3.x

**Assignment:**

·
Exercise
1.19

·
Exercise
1.21

**September
18**

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

**Assignment:**

- Make sure you understand the formulation (statement) of
the pumping lemma and can accurately reproduce it. No proof of this lemma
is required tough.
- 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).

**September
23**

**Material covered:
**Nothing new

**Assignment: **Nothing new

**September
25**

**Material covered:
**Slides 2.1.a – 2.1.i

**Assignment: **

- Exercise 2.1
- Exercise 2.3 (a-n)
- When do we say that a context-free grammar is
ambiguous? (definition)
- Exercise 2.4
- Exercise 2.9

**September
30**

**Material covered:
**Slides 2.1.i – 2.2.e

**Assignment: **

- Using the procedure of Slide 2.1.j, convert the DFA
from Exercise 1.1 to an equivalent context-free grammar.*M*_{1} - Construct a PDA for the language
**{w#w**^{R}^{ }| w**Î{0,1}*}**. Here and below,**w**means^{R}**w**spelled right to left. So, the strings in this language are**#**,**0#0**,**1#1**,**00#00**,**01#10**,**10#01**,**11#11**,**000#000**,**001#100**,**111001****#100111**, etc. - Construct a PDA for the language
**{w | w=w**^{R}, i.e., w is a palindrome**}**. Assume the alphabet is**{0,1}**. - Construct a PDA for the language
**{w | the length of w is odd and its middle symbol is a 0}**. Assume the alphabet is**{0,1}**.