CSC
4170: Homework Questions
Policy: Homework will not be graded, but the quiz and examination questions will mostly come from or be based on the homework assignments. Using somebody's help when doing homework is not forbidden. Books or notes will not be allowed during a quiz or examination.
[For the quiz of August 29]
Material covered: Slides 0.a – 0.h
Questions: (New questions will/may be added to this list on Thursday)
· 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 0.6
[For the quiz of September 5]
Material covered: Slides 1.1.a – 1.2.g
Questions: (New questions will/may be added to this list on Thursday)
· Exercise 1.1
· Exercise 1.2
· Exercise 1.3
· If a DFA (finite automaton) does not accept any strings, how many (if any) languages can it recognize?
· 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)
[For the quiz of September 12]
Material covered: Slides 1.2.h – 1.3.d
Questions: (New questions will/may be added to this list on Thursday)
· Exercise
1.16
· What
is a regular expression over an alphabet S? (define –
Slide 1.3.b)
· List
all the elements of the set ({a,b}°{0,1})È({a,b}°Æ*)È({0,1}°Æ).
· List
five distinct elements of the set {01,10}*.
· Exercise
1.18 (a,b,c,d,e,g,k,l,m,n)
· Exercise
1.20
[For the quiz of September 19]
Material covered: Slides 1.3.e – 1.4.c
Questions: (New questions will/may be added to this list on Thursday)
· Exercise 1.19
· You should be able to perform the routines of ripping a
state out (Slide 1.3.q) and eliminating parallel transitions (Slide 1.3.r).
· Exercise 1.21
· Make sure you understand the formulation (statement) of the
pumping lemma and can accurately reproduce it. No proof of this lemma is
required though.
[For the quiz of September 26]
Material covered: Slides 1.4.c – 2.1.i
Questions: (New questions will/may be added to this list on Thursday)
· 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).
· Exercise
2.1
· Exercise
2.3
· When
do we say that a context-free grammar is ambiguous?
(definition)
· Exercise
2.4
· Exercise
2.9
[For the quiz of October 3]
Material covered: Slides 2.2.a – 2.3.d
Questions: (New questions will/may be added to this list on Thursday)
· 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 | the length of w is odd and
its middle symbol is a 0}
over
the alphabet {0,1}.
· 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.
· Construct a PDA
for the language {wwR | w∈{0,1}*}.
· Construct a PDA
for the language {w | w=wR, i.e., w is a
palindrome} over the
alphabet {0,1}.
· Construct a PDA
for the language {w | the length of w is odd and
its middle symbol is a 0}
over
the alphabet {0,1}.
· State the pumping
lemma for context-free languages.
· Using the pumping
lemma, prove that the language {anbncn | n≥0}
is
not context-free.
[For the quiz of October 17]
Material covered: Slides 3.1.a – 3.1.g
Questions: (New questions will/may be added to
this list on Thursday)
·
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,=}.
[For the quiz of October 24]
Material covered: Slides 3.1.h – 3.2.c
Questions: (New questions will/may be added to
this list on Thursday)
[For the quiz of October 31]
Material covered: Slides 3.2.d – 3.2.j
Questions: (New questions will/may be added to
this list on Thursday)
[For the quiz of November 7]
Material covered: Slides 3.2.h – 4.1.a
Questions: (New questions will/may be added to
this list on Thursday)
[For the quiz of November 14]
Material covered: Slides 4.1.b – 4.2.d
Questions: (New questions will/may be added to
this list on Thursday)
·
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)
·
Prove that if a language L and its complement L are both
recognizable, then L is decidable (Theorem 4.22).
·
Prove that the complement of ATM is not recognizable
(Theorem 4.23).
·
Is the complement of ATM decidable? Why or why not?
[For the quiz of November 21]
Material covered: Slides 5.1.a – 7.1.g (Section 6 is omitted. Slides 7.1.c-7.1.g are just to help you refresh your memory of asymptotic analysis, depending on your needs).
Questions: (New questions will/may be added to
this list on Thursday)
Your answers should start with “f(w) = ”
[For the quiz of November 28]
Material covered: Slides 7.1.h – 7.1.p
Questions: (New questions will/may be added to
this list on Thursday)
[For the quiz of December 5]
Material covered: Slides 7.2.a – 7.3.g
Questions: (New questions will/may be added to
this list on Thursday)
Additional material covered since the previous posting: Slides 7.3.d – 8.3.e
Questions:
FINAL EXAM: Wednesday December
13, 11:30-2:00, Mendel 213.