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

**October
2**

**Material covered:
**Slides 2.3.a – 3.1.c1

**Assignment: **

- The formulation (no proof) of the pumping lemma for
context-free languages.
- Proof given in Example 2.36 (Slide 2.3.c).
- The definitions of “decider”,
“recognize” and “decide” (Slide 3.1.c1).
- Exercise 3.2
- Exercise 3.5

**October
7**

**Material covered:
**Slides 3.1.c2 – 3.1.j

**Assignment: **

- Construct a Turing machine (provide a full diagram)
that decides the language represented by the regular expression
The input alphabet here is*#0*=0*.**{#,0,=}**.* - Construct a Turing machine (provide a full diagram) for
the language
*{#**·*^{n}*>**·*^{m }*| n>m}* - Design a fragment of a TM
that, from a state “
”, goes to a state “*Beg?*” or “*Yes*”, depending on whether you are at the beginning of the tape or not, without corrupting the contents of the tape (Slide 3.1.i).*No*

·
Design a fragment of a TM that, from a state
“** Go to the beginning**”, goes
to the beginning of the tape and state “

**October
9**

**Material covered:
**Slides 3.1.k – 3.2.d

**Assignment: **

·
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

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

**October
21**

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

**Assignment: **

· State Theorem 3.16 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.

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

· Exercise 3.6.

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

**October
23**

**Material covered:
**Slides 3.2.j – 3.2.k

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

**October
28**

**Material covered:
**Slides 3.3.a – 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.

**October
30**

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

**Assignment: **

· Exercises 4.1, 4.2, 4.3.

**November
4**

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

**Assignment: **

- What language does the universal Turing machine
recognize? (Do not just give its name, define the language.) The answer is
found on Slide 4.2.a.
- How does the universal Turing machine work? (I.e. what
algorithm does it follow?) The answer, again, is 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).
- Proof of Theorem 4.23.

**November
6**

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

**Assignment: **

- 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).
- 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) a
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
11**

**Material covered:
**Slides 5.3.d, 6.3.a and 6.3.b (Section 6.2 will be covered later)

**Assignment: **

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

**November
13**

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

**November
18**

**Material covered:
**Slides 6.2.d - 7.1.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).

· Definition 7.1.

**November
20**

**Material covered:
**Slides 7.1.b - 7.1.m (slides 7.1.c-7.1.g omitted)

**Assignment: **

- Show that
**{0**^{k}1^{k}| k**³****0}ÎTIME(n log n)**(describe a TM and give an asymptotic analysis).

**November
25**

**Material covered:
**Slides 7.1.n – 7.2.d

**Assignment: **

- Theorems 7.8, 7.11 with proof ideas.
- Definitions 7.9, 7.12.
- What are the two main reasons making the class
**P**important and appealing? (Slide 7.2.a) - Give a polynomial time algorithm for
**PATH**(Slide 7.2.d). Explain why it indeed runs in polynomial time. - Exercise 7.8.
- Exercise 7.9 (the meaning of “clique” is
explained at the end of page 295).

**December
2**

**Material covered:
**Slides 7.2.e – 7.3.f

**Assignment: **

· Show that the RELPRIME
problem is in P (Slide 7.2.f).

· Define the class NP (Slide 7.3.d).

· Show that the CLIQUE problem is in NP (Slide
7.3.e).

· Show that the SUBSET-SUM problem is in NP (Slide
7.3.f)

· Show that the COMPOSITES problem is in NP (as
in the previous two cases, you will need to do this by constructing a
polynomial time nondeterministic TM).

**December
4**

**Material covered:
**Slide 7.3.g, and a brief survey of space complexity

**Assignment: **

- The
definitions of coNP and EXPTIME
(given on slide 7.3.g).
- The
intuitive characterizations of P, NP, coNP and EXPTIME (given on slide 7.3.g).
- What
do we know and what do we not know about the relationships (equal?
subset?) between P, NP, coNP, EXPTIME? (again, given on slide 7.3.g).

· True or false? (1) Some languages from EXPTIME are undecidable. (2) Every regular language is in P. (3) The complement of a recognizable language is always recognizable. (4) Every context-free language is generated by some unambiguous context-free grammar. (5) Every regular language is context-free. (6) Every regular language is in NP. (7) The complement of a decidable language is always decidable. (8) Turing reducibility implies mapping reducibility. (9) Every language from NP is decidable. (10) The complement of any language from P is also in P. (11) Every language that is decided in polynomial time by some multitape TM is also decided in polynomial time by some single-tape TM. (12) Every context-free language is in P. (13) PATH is in NP.

·
Prove that the halting problem HALT_{TM} is undecidable.