Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CS 3800

Homework 7

Spring 2024

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) {a n b m | n ≤ m}.

(b) {a n b m | n ≥ m}.

2. [6 Points] Pushdown. Construct a pushdown automaton P such that (assume m, n ≥ 0):

L(P) = {a mb n | 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) = {a mb n | 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 = {a n b m | n > m and n is even}

Clearly L = Lcf l ∩ Lreg where

Lcf l = {a n b m | n > m} and Lreg = {w ∈ {a, b}* | w has an even number of a’s}

(a) Draw the state diagram of a DFA for Lreg. For full credit, your automaton should have as few states as possible.

(b) Draw the state diagram of a PDA for Lcf l. 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

{a n b m | n ≤ m} and {a n b m | n ≥ m}

are context-free. Use this fact to give very simple proofs that

{a n b m | n < m} and {a n b m | n > m}

are context-free.

(b) Prove that the language

{a, b}* − {a n b n | n ∈ N}

is context-free.

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 = u v x y z

such that

i. |v x y| ≤ p

ii. v ≠ ε

iii. u vn x yn z ∈ L for all n ≥ 0

Your proof should be simple and succint. References to problem 2.37 in the textbook will not be accepted.

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 = {a n b 2n c k | n > k ≥ 0}

is not context free.

(a) Suppose (for contradiction) that L is context free. Then it has a pumping length p ≥ 1. Why is p ≥ 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 = a p b 2p c p−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} ∗ }

is not context-free.

(a) Use the pumping Lemma to show that the language {a n b an b an b | n ≥ 1} is not context free.

(b) Use closure properties of CFLs to conclude that L is not context-free. (Don’t give a direct proof.)