CSC 4170-002: 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
29
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
September
5
Material covered:
Slides 1.1.a - 1.2.k
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
12
Material covered:
Slides 1.2.l - 1.3.j
Assignment:
Exercise 1.16
Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
Exercise 1.20
Exercise 1.19
September
19
Material covered:
Slides 1.3.k - 1.4.e
Assignment:
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 {0n1n
| 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 {0m1n
| 0<m<n} is not regular.
- Using
the pumping lemma, prove that the language {0m1n
| 0<n<m} is not regular (hint: think of pumping out
instead of pumping in).
September
26
Material covered:
Slides 2.1.a – 2.2.b10
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
- Using the
procedure of Slide 2.1.j, convert the DFA M1 from Exercise
1.1 to an equivalent context-free grammar.
- Construct
a PDA for the language {w#wR
| w∈{0,1}*}. Here
and below, wR
means 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.
October
3
Material covered:
Slides 2.2.c – 3.1.e1
Assignmtent:
- Construct
a PDA for the language {w | w=wR, 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)
- The
definitions of “decider”, “recognize” and
“decide” (Slide 3.1.c1).
- Exercise
3.2
- Exercise
3.5
October
17
Material covered: Slides 3.1.e1
– 3.2.d NOTE: Due to your
instructor’s absence, there will be no class on Thursday October 19.
Assignmtent:
- 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,=}.
- Construct
a Turing machine (provide a full diagram) for the language {#0n>0m | n>m}. The input alphabet here is {#,0,>}. (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.
- 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
24
Material covered: Nothing new. NOTE:
Even though no new material was added last week, there will still be a quiz on
October 24 as usual.
Assignmtent: Nothing new.
October
31
Material covered: Slides 3.2.e-3.3.c
Assignmtent:
State
Theorem 3.16 and provide a very brief (a few lines perhaps) 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.
- The
definitions of computing, computability and graph of a function (Slide
3.2.j).
- Proof idea
for the theorem on Slide 3.2.k.
- What
is encoding? Give examples.
November
7
Material covered: Slides 3.3.d – 4.1.c
Assignmtent:
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).
Exercises
3.7, 4.1(a,b,c) 4.3.
Prove that if
a language is decidable, then so is its complement.
Prove that if
two languages are decidable, then so is their intersection.
November
14
Material covered: Slides 4.1.d – 4.2.d
Assignmtent:
Exercise 4.3. Hint: similar to Theorem 4.4.
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.
- Prove
that if a language L and its
complement L are both
recognizable, then L is
decidable (Hint: the idea is, in fact, already given in the proof of
Theorem 4.23).
November
21
Material covered: Slides 5.1.a, 5.3.a-5.3.d,
6.3.a-6.3.b
Assignmtent:
·
Prove that the halting problem is undecidable
(Theorem 5.1)
·
Prove that the halting problem is undecidable
(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.
·
Prove that if a language A is
mapping reducible to a language B and B is
decidable, then A is decidable (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}
·
When do we say that a language A is decidable
relative (i.e. Turing reducible) to a language
B?
·
Prove that if a language A is
Turing reducible to a language B and B is
decidable, then A is decidable (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
28
Material covered: Slides 6.2.a-6.2.d
Assignmtent:
- Remember that ∃xA
(“there exists x such that A”) is an
abbreviation of ¬∀x¬A.
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)∨∨ {\displaystyle
\lor } B and ∃xA(x) as an
abbreviation of ¬∀x¬A(x)):
(1) "x is even''; (2) "x≥y"; (3) "x>y";
(4) "x=y3"; (5) "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
7
(yes, the quiz has moved from Dec.5 to Dec.7)
Material covered: Slides 7.1.a-8.2.a
Assignmtent:
NOTE: Go to the Lecture Notes
page to find the newly added notes for Chapter 8 and the updated notes for
Section 7.3.
·
Definitions 7.1, 7.7, 7.9, 7.12.
·
Describe a O(n2) time TM
which decides the language {0n1n
| n≥0} (Slide 7.1.b).
·
Answer the questions of Slide 7.1.j.
- Show
that {0n1n | n≥0} is in TIME(n log n) (describe a TM and give an asymptotic analysis).
·
Theorems 7.8, 7.11 withOUT
proofs.
- 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.c). Explain why it indeed
runs in polynomial time.
- Exercises
7.3, 7.8, 7.9.
·
Define the class NP (Slide 7.3.d).
·
Show that the CLIQUE problem is in NP (Slide 7.3.e).
- The
definitions of coNP and EXPTIME
(given on slide 7.3.i).
- The
intuitive characterizations of P, NP, coNP and EXPTIME (given on slide 7.3.i).
- 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).
- Define
the space complexity of a machine (Slide 8.0.a).
·
Define
the class PSPACE (Slide 8.2.a).
·
Give
a linear space algorithm for SAT (Slide 8.0.c).
·
What
does Savitch’s theorem say? (Slide 8.1.a).