CS 3800 代做、代写 Python ，java 程序设计

日期：2024-03-17 09:37

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.

Page 3 of 3