[syllabus] | [lecture notes] | [HW1-6,Q1] | [HW7-10,Q2,F] | [project]
[simulators/parsers] | [language definitions] | [automata definitions] | [computable definitions]
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: 5.1 5.2 7.1 7.3 7.4 Exam covers homework: HW5 and HW6 Exam covers lectures: 12 -18
1) Construct a NPDA equivalent to the following grammar:
G = ( {S, A}, {a, b}, P, S )
Productions
S -> a A A
A -> a S | b S | a
Define all the components M = ( Q, Sigma, Gamma, delta, q0, Z0, F)
Show your work, partial credit given
2) Construct a grammar equivalent to the following PDA
M = ({q0, q1}, {0,1}, {Z0, X}, delta, q0, Z0, phi)
delta Sigma input, Gamma Top of stack
| 0,Z0 | 0,X | 1,Z0 | 1,X | eps,Z0 | eps,X
----+-----------+----------+------------+------------+------------+--
q0 | phi | {(q1,X)} | {(q0,XZ0)} | {(q0,XX)} | {(q0,eps)} | phi
q1 | {(q0,Z0)} | phi | phi | {(q1,eps)} | phi | phi
eps is short for epsilon the null string.
Define all components G = ( V, T, P, S)
Show your work, partial credit given
You are allowed to use the executable 'cykp' and copy the V table.
You are allowed to look at C++ code in cykp.cpp
1) Given the CFG G = ( {S, A, B, C}, {a, b}, P, S
with Productions
S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a
Determine if these strings are in the language:
a) aaaaa
b) aaaaaa
c) baabab
You must show the V table.
Hint: use hw8.g and cykp.
2) Let G be a CFG in Chomsky Normal Form
Give an algorithm to determine the number of distinct
derivations of a string x.
You must show neat pseudo code with comments
You have complete freedom on how to proceed.
One method is to assume the five-tuples from lecture 24
are in the sets in the V matrix. Systematically walk
the indexes and keep a count of successful walks.
1) write out the steps 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, including
delta transition table 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. tape 000#b
P.S. 3 squared is nine 000000000#b
Hint: copy the input string as many times as there are 0's
on the tape at the start.
Code your program and test it using the Turing Machine simulator,
"tm" The name of your program is to be 'square.tm'
More details are found in Simulators.
Submit your homework on gl using submit cs451 hw10 square.tm
or EMail or turn in on paper.
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 NPDA
did not have to be able to recognize L ?
(You can answer part 2 as a comment in square.tm)
Closed book. Covers all lectures, all reading assignments, all homework
and project. Multiple choice and short answer questions.
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 Turing machines,
and grammars and regular expressions
4) Understand the statement of the Pumping Lemma for Context Free Languages
5) Understand the Halting Problem and why it is not computable
6) Understand the Church Turing Hypothesis
last updated 5/5/04