The most important item on all homework is YOUR NAME! No name, no credit. Staple or clip pages together.
Homework must be submitted when due. You loose 10%, one grade, the first day homework is late. Then 10% more per week, each week homework is late. Max of 50% off. A ZERO really hurts your final points. Do and turn in all homework, even if it is late. Paper or EMail to squire@cs.umbc.edu is acceptable. If I can not read or understand your homework, you do not get credit. Type or print if your handwriting is bad. Homework is always due on a scheduled class day within 15 minutes after the start of the class. If class is canceled then homework is due the next time the class meets.
EMail only plain text! No word processor formats.
You may use a word processor or other software tools and
print the results and turn in paper.
Closed book. Multiple choice questions based on lectures,reading assignments and homework. Exam covers book: 4.1 - 4.6 Exam covers homework: HW5 and HW6
Book, Page 143, 6.17 related to project, you must show the V table of
fig 6.10
Book, Page 143, 6.18 a) you must show neat pseudo code with comments
Book, page 120, exercise 5.2 show your work, partial credit given book, page 121, exercise 5.6 show your work, partial credit given
1) write out the steps for example 6.1, page 127, using the
pumping lemma for CFL's to prove that
i i i
L = { a b c | i >= 1 } is not a CFL.
2) Using the steps in 1) [go back and add more if you missed some],
prove, using the pumping lemma for CFL's that
i j k
L = { a b c | i < j < k } is not a CFL.
1) Write the machine description for a Turing machine and draw
the corresponding diagram for the specific machine that
starts with a number n on the tape and finishes with
n squared on the tape. n on the input is just n zeros followed
by blank tape. To save many hours of time, use English text of
pseudo code in place of the delta transitions. (Still give
a reasonable estimate of states, list reasonable set for Gamma.
Give specific values or sets for rest of description.)
2) L = { ww | w in Sigma star } is not a CFL.
L is recognized by a Turing machine.
What essential feature does a Turing machine have that a PDA
did not have to be able to recognize L ?
1) go over the Quiz 1 and Quiz 2
the final exam will include some of these questions
2) You may find it helpful to go over the
Lecture Notes but not the details of constructions
3) Understand what classes of languages go with what machines (automata)
and grammars and regular expressions
4) Understand the statement of the Pumping lemma for Context Free Languages
Last updated 11/26/98