**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 (90%) come from the homework
assignments. Books or notes will not be allowed during the quiz.

**August
27**

**Material covered:
**Slides 0.a - 0.h

**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

**August
29**

**Material covered:
**Slides 1.1.a - 1.1.j

**Assignment:**

·
Exercise 1.1

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

**September
3**

**Material covered:
**Slides 1.2.a - 1.2.h

**Assignment:**

- Exercise 1.7(a,b,c,d,g)
- Exercise 1.24
- Exercise 1.27

**September
5**

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

**Assignment:**

- Exercise 1.16

**September
10**

**Material covered:
**Slides 1.3.a – 1.3.d

**Assignment:**

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

**September
12**

**Material covered:
**Slides 1.3.e – 1.3.p

**Assignment:**

- Exercise 1.19

**September
17**

**Material covered:
**Slides 1.3.q – 1.3.x

**Assignment:**

- Exercise 1.21
- Exercise 1.24
- Exercise 1.27

**September
19**

**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
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
24**

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

**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
26**

**Material covered:
**Slides 2.1.h – 2.1.k

**Assignment:**

- Using the procedure of Slide 2.1.j, convert the DFA from Exercise 1.21(b) to an equivalent
context-free grammar.

**October
1**

**NOTICE: a) The Oct.3 class cancelled; b)
There will be 5 quizzes at once on Oct.8. Today’s material will not be
included. **

**Material covered:
**Slides 2.2.1 – 2.3.d

**Assignment:**

- 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}**. - The formulation (no proof) of the pumping lemma for
context-free languages.
- Proof given in Example 2.36 (Slide 2.3.c).

**October
10**

**Material covered:
**Nothing new, just a review.

**Assignment: **Enjoy your Fall break.** **

**October
22**

**Material covered:
**Slides 3.1.a – 3.1.d

**Assignment: **

- The definitions of accepting, rejecting, recognizing,
deciding (Slide 3.1.c1).
- Exercise 3.2
- Exercise 3.5
- Construct a Turing machine (provide a full diagram)
that decides the language represented by the regular expression
**#0*=0*.**The input alphabet here is**{#,0,=}**.

**October
24**

**Material covered:
**Slides 3.1.e1 – 3.1.l

**Assignment: **

- Construct a Turing machine (provide a full diagram) for
the language
**{#****·**^{n}**>****·**^{m }**| n>m}**(note: this is similar to but NOT the same as the example on slide 3.1.f). - Design a fragment of a TM
that, from a state “Beg?”, goes to a state “Yes” or
“No”, depending on whether you are at the beginning of the
tape or not, without corrupting the contents of the tape (Slide
3.1.i).

· Design a fragment of a TM that, from a state “Go to the beginning”, goes to the beginning of the tape and state “Done” (Slide 3.1.j).

· Design a fragment of a TM that, beginning from the current cell, shifts the contents of the tape right, typing in the current cell a 0 (Slide 3.1.k). Assume the tape alphabet is {0,1,-}, and that neither 0 nor 1 ever occurs after the leftmost blank on the tape.

**October
29**

**Material covered:
**Slides 3.2.a – 3.2.e

**Assignment: **

· Design a fragment of a 2-tape TM that swaps the contents of the tapes, from the position where the heads are at the beginning and there are no blanks followed by non-blank symbols (Slide 3.2.c). Tape alphabet: {0,1,-}.

· State Theorem 3.13 and provide a very brief (half-page or so) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.

· The same for Theorem 3.16.

**October
31**

**Material covered:
**Slides 3.2.f – 3.2.h

**Assignment: **

- Proof of Theorem 3.21.
- Design an enumerator for the language
**(00)***, i.e.**{****e****,00,0000,000000,00000000,…}**. Hint: Start with the one of Slide 3.2.g and think about how to (slightly) modify it.

**November
5**

**Material covered:
**Slides 3.2.i – 3.3.b

**Assignment: **

· The definitions of computing, computability and graph of a function (Slide 3.2.j).

· Proof idea for the theorem on Slide 3.2.k.

·
For a bit string **w**,
**NOT(w) **means **w**
with all bits changed. For example, **NOT(11010)=00101**.
Construct a Turing machine with an output that computes function **NOT**.

· Exercise 3.6.

**November
7**

**Material covered:
**Slides 3.3.b –
3.3.f

**Assignment: **

· What is encoding? Give examples.

· What is the Church-Turing thesis all about? (don't just write something like "algorithms = TM"; write a couple of sentences showing that you understand what you are writing).

· Exercise 3.7.

**November
12**

**Material covered:
**Slides 4.1.a –
4.1.f

**Assignment: **

· Exercises 4.1, 4.2, 4.3.

**November
14**

**Material covered:
**Slides 4.2.a –
4.2.b.2

**Assignment: **

- What language does the universal Turing machine
recognize and how does it work? (the description of the algorithm it
follows). Answers to this question are found on Slide 4.2.a.
- Proof of Theorem 4.11 (Given on Slides 4.2.b.1-2, or page 207 of the textbook).

**November
19**

**Material covered:
**Slides 4.2.c – 5.1.a

**Assignment: **

- Proof of Theorem 4.23.
- Prove that if a language
**L**and its complementare both recognizable, then__L__**L**is decidable (Hint: the idea is, in fact, already given in the proof of Theorem 4.23). - Proof of Theorem 5.1.
- Prove that the halting problem is recognizable (Hint:
similar to the theorem on Slide 4.2.a).

**November
21**

**Material covered:
**Slides 5.3.a – 5.3.d

**Assignment: **

- The definitions of mapping reduction and mapping
reducibility.
- Proof of Theorem 5.22.
- Prove that if a language
**A**is mapping reducible to a language**B**and**B**is recognizable, then**A**is recognizable (hint: very similar to the proof of Theorem 5.22). - In each case below, find (precisely define) particular
function that is a mapping reduction of
**A**to**B**. Both**A**and**B**are languages over the alphabet**{0,1}**. **A**is the language described by**1*0***,**B**is the language described by**01*0*****A={w**| the length of w is even**}**,**B**=**{w**| the length of**w**is odd**}****A=B={w**| the length of**w**is even**}****A={0,1}***,**B={00,1,101}**

**November
26**

**Material covered:
**Slides 6.2.a – 6.2.c

**Assignment: **

- Which of the following sentences are true and which are
false? Justify your answers:

1.**"****x****$y****(x=y)**2.

**$****y****"****x****(x=y)**3.

**"****x****"****y****(****$****z****(****y****=x+z)****Ú $****z(x=y+z))**

- Express, using the formal language of arithmetic (given
on Slide 6.2.a), the following (it is OK if you use
**x**,**y**,**z**,.. instead the official variables**v**,**v'**,**v''**, ...; it is also OK to use**A®B**as an abbreviation of**(****Ø****A****)Ú****B**and**$****xA****(x)**as an abbreviation of**Ø"****x****ØA****(x)**):

(1) "**x**is even''; (2) "**x****³y**"; (3) "**x>y**"; (4) "**x=y**"; (5) "^{3}**x**is composite" (meaning that x is the product of two other numbers, both different from**x**); (6) "**x**is prime"; (7) "**x**is a divisor of**y**"; (8) "**x**is a common divisor of**y**and**z**"; (9) "**x**is the greatest common divisor of**y**and**z**". NOTE: In order for the translation to be adequate, it should have exactly the same free variables as the original statement; all other variables of the translation should be bound.

**December
3**

**Material covered:
**Slides 6.2.d – 6.3.b

**Assignment: **

- Prove that
**Th****(****N,+,****´****)**is unrecognizable, assuming that the undecidability of this problem is already known (the Corollary on slide 6.2.d). - The definition of Turing reducibility.
- Proof of Theorem 6.21.
- Show that any language
**L**is Turing reducible to its complement (Hint: A straightforward generalization of the example on Slide 6.3.a). - Prove that, whenever a language
**A**is mapping reducible to a language**B**, then**A**is also Turing reducible to**B**.

**December
5**

**Material covered:
**Slides 7.1.a – 7.2.e (Slides 7.1.c-7.1.g, 7.2.b omitted; the
proofs of Theorems 7.8 and 7.11 also omitted)

**Assignment: **

- Definitions 7.1, 7.9, 7.12.
- Show that
**{0**^{k}1^{k}| k**³****0}ÎTIME(n log n)**(describe a TM and give an asymptotic analysis). - Show that PATHÎP (Theorem 7.14).