Exam 2
DUE: April 15 at 11:59pm on CourseSite
CSE 318: Spring 2020
Important: This exam is take home. You may use your notes and homework, my completed notes and homework solutions posted on CourseSite, our class text book, and any material posted in our remote en- vironment (e.g., recorded Zoom lectures). However, you may not consult other text books, resources (on- and offline), or other people. This includes outside solutions (full and in part) made available by professors or students, both at Lehigh or other institutions. You may not collaborate with other people, both in the class and outside of class. Exams will be carefully checked for any evidence of plagiarism, and any academic integrity violations will be immediately reported. You may use the entire time allotted (one week), however, please note that this exam is not intended to take seven full days. If you find you are spending a lot of time on any one question, please contact Professor Carr with any questions.
By submitting your work, you are affirming that you have neither given nor received any unauthorized aid on this exam.
This exam is out of 150 points. Complete all questions. Where appropriate, please show details of your work to allow for possible partial credit.
SUBMISSIONS: You must submit your written (or typed) solutions as a single pdf, and any JFLAP files must be compressed into a single zip file. Please name any JFLAP files you submit (not the zip file, the files within it) descriptively enough that I know which problems they correspond to. Late submissions will not be accepted.
Please write all solutions on separate sheets of paper and clearly indicate which questions you are answering.
1
1. (20 points) Construct the grammars that generate the following languages (a) L1 ={anbman |n,m>0}
(b) L2 ={anbmcmd2n |n≥0,m>0}
2. (15 points) Convert the following context-free grammar to Chomsky normal form, given by the rules:
S → AB | BDS A → aA | D
B → bbB | b
D → dD | λ
3. (20 points) Consider the following rules for a CFG:
S → bS | Sb | a
(a) Using the string w = bab, show that the language generated by this CFG is ambiguous.
(b) We say that a grammar is inherently ambiguous if it cannot be converted to an equivalent un- ambiguous grammar. Determine whether the grammar given above is inherently ambiguous or not.
4. (20 points) Consider L3 = {w ∈ {a, b}∗ | |w| is even and w contains an odd number of a’s} (a) Construct a DFA that recognizes L3.
(b) Convert this DFA to a PDA.
5. (10 points) Consider L4 = {aibj | 2i = 3j} and L5 = {aibj | 2i ̸= 3j}. Build a PDA to recognize
L4 ∩L5.
6. (20 points) Consider L6 = {wdwR | w ∈ {a, b, c}∗}.
(a) Construct a PDA with only two stack elements that recognizes the language L6. (b) Provide a sample string in L6 and trace its computation.
7. (15 points) Using the pumping lemma, show L7 = {aibjaibj | i,j ≥ 0} is not context-free.
8. (15 points) Consider L8 = {ww | w ∈ {a, b}∗}. Without using the pumping lemma prove that L8 is not context-free. (Hint: consider the regular expression a∗b∗a∗b∗, L7 above, and the closure properties of CFLs.)
9. (15 points) Consider the following Turing Machine from our lecture notes (see Lecture 11, pages 3-4).
(a) Carefully describe this language. Is it regular? Context-free? Briefly justify your response.
(b) Briefly explain why we can construct a Turing Machine for a language we know is context-free or regular.
2
(c) Trace the computation of a string accepted by this machine (you may use the tape to visualize this computation or the yields relation). Use a string that differs from the one in the lecture notes.
(d) Recall that we said this Turing machine accepts by halting. Modify it to accept by final state.
3