CS 3800-Online W. Schnyder
Spring 2024 3/6/2024
Homework 7 (due Friday, March 15)
Instructions: This homework is to be submitted on GradeScope as a single pdf (not in parts) by 11:59 pm on the due date. You may either type your solutions in a word processor and print to a pdf, or write them by hand and submit a scanned copy. Do write and submit your answers as if they were a professional report. There will be point deductions if the submission isn’t neat (is disordered, difficult to read, scanned upside down, etc. . . .).
Begin by reviewing your class notes, the slides, and the textbook. Then do the exercises below. Show your work. An unjustified answer may receive little or no credit.
Read: 2.3 (for Tuesday) and 3.1 (for Friday)
1. [8 Points] Pushdown. For each of the following languages over the alphabet {a, b}, draw the state diagram of a pushdown automaton that accepts this language. For full credit, your automaton should have as few states as possible. (Below, assume that m, n ≥ 0).
(a) {anbm | n ≤ m}. (b) {anbm | n ≥ m}.
2. [6 Points] Pushdown. Construct a pushdown automaton P such that (assume m, n ≥ 0): L(P)={ambn |n=2m}
Specify the components of your automaton and draw a state-diagram. For full credit, your automaton should have as few states as possible.
3. [6 Points] Pushdown. Construct a pushdown automaton P such that (assume m, n ≥ 0): L(P)={ambn |m≤n≤2m}
Specify the components of your automaton and draw a state-diagram. For full credit, your automaton should have as few states as possible.
4. [15 Points] Intersection. Consider the language (n and m are natural numbers ≥ 0) L={anbm |n>mandniseven}
Clearly L = Lcf l ∩ Lreg where
Lcfl ={anbm |n>m}andLreg ={w∈{a,b}∗ |whasanevennumberofa’s}
(a) Draw the state diagram of a DFA for Lreg. For full credit, your automaton should have as few states as possible.
Page 1 of 3
CS 3800-Online HW 7 Spring 2024
(b) Draw the state diagram of a PDA for Lcfl. For full credit, your automaton should
have as few states as possible.
(c) Apply the algorithm from class (lecture 15d) to construct a PDA for L. Draw the state diagram of your automaton. (Do not delete useless states, this problem only asks you to demonstrate your understanding of the algorithm.)
5. [8 Points] Closure properties. In this problem, you are not allowed to construct gram- mars or automata. Everything can be shown using closure properties. Throughout, the reference alphabet is Σ = {a,b} and N denotes the natural numbers (including 0); and n, m ∈ N.
(a) In Problem 1, you showed that the languages
{anbm |n≤m} and {anbm |n≥m}
are context-free. Use this fact to give very simple proofs that {anbm |n<m} and {anbm |n>m}
are context-free.
(b) Prove that the language
{a,b}∗ −{anbn |n∈N}
6. [6 Points] Closure Properties. Suppose that L is context-free and R is regular.
(a) Is L − R necessarily context-free? Justify your answer. (b) Is R − L necessarily context free? Justify your answer.
7. [5 Points] Pumping Lemma. Prove the following variant of the Pumping Lemma:
For each context-free language L there exists a pumping length p ≥ 0 such that each word
w with w ∈ L and |w| ≥ p can be written as w=uvxyz
such that
i. |vxy|≤p ii. v̸=ε
iii. uvnxynz∈Lforalln≥0
Your proof should be simple and succint. References to problem 2.37 in the textbook will not be accepted.
is context-free.
Page 2 of 3
CS 3800-Online HW 7 Spring 2024
8. [9 Points] Pumping Lemma. This problem leads you step-by-step through a Pumping Lemma based proof (the next problems will not indicate the steps). You will show that the language
L={anb2nck |n>k≥0}
(a) Suppose (for contradiction) that L is context free. Then it has a pumping length
is not context free.
p≥1. Whyisp≥1?
(b) Every word w ∈ L with length |w| ≥ p can be written as w = uvxyz with three properties. What are these three properties?
Select the word w = apb2pcp−1
(c) Derive a contradiction in case v begins with a. (d) Derive a contradiction in case v begins with b. (e) Derive a contradiction in case v begins with c.
(f) Use problem 7 to explain that the above proof is complete.
9. [8 Points] Pumping Lemma. In this problem, you will show that the language
L = {www | w ∈ {a,b,c}∗}
(a) Use the pumping Lemma to show that the language {anbanbanb | n ≥ 1} is not
is not context-free. context free.
(b) Use closure properties of CFLs to conclude that L is not context-free. (Don’t give a direct proof.)
10. [0 Point] Do not submit. Exercise 2.6(ac) page 155. The solution is in the book page 160, this is for practice only.
11. [0 Point] Do not submit. Exercise 2.7(ad) page 155. The solution is in the book pages 160, this is for practice only.
12. [0 Point] Do not submit. Exercise 2.8 page 155. The solution is in the book page 161, this is for practice only.
13. [0 Point] Do not submit. Problem 2.18 page 156. The solution was covered in lecture and is also in the book page 161, this is for practice only.
請加QQ：99515681 郵箱：99515681@qq.com WX：codehelp
