[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.
Turn in paper any class or under door ITE 226 Email to: squire@umbc.edu 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. Use the same technique for plain text as is used in this WEB page. Write out Greek letters, a plus means union in expressions, a star after an expression is a Kleene star, see Language definitions Submit (on linux.gl.umbc.edu) submit cs451 hw1 your-file-or files This may help by not allowing Email to screw up format.
Closed book. Multiple choice questions based on lectures, and homework. Exam covers lectures: 12 -18 Exam covers homework: HW4, HW5, HW6
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.
No work required for Summer Session, automatic 25 points
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
Note: 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 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 6/6/12