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.)