2-hw: Nonregular Languages and Context-free Languages
CSE105SP20
Due: Sunday May 3 at 11:00PM (on Gradescope)
The same homework policies apply as in 1-hw. Please see that assignment writeup for details about
• Collaboration policy and group size.
• Submission instructions.
• Typed work.
• Expectations for justification
Reading and extra practice problems: Sipser Section 1.4, 2.2. Chapter 1 exercises 1.29, 1.30.
Chapter 1 problems 1.49, 1.50, 1.51. Chapter 2 exercises 2.5, 2.7.
Key Concepts: Pumping lemma, nonregular sets, pushdown automata (PDA), stack.
1. In class and in the reading so far, we’ve seen the following examples of nonregular sets:
{0n1n | n ≥ 0}
{0n1n | n ≥ 2}
{0n1m | 0 ≤ n ≤ m}
{0n1m | 0 ≤ m ≤ n}
{0i12i | 0 ≤ i}
{0i1i+1 | 0 ≤ i}
{0n1m0n | n,m ≥ 0}
{w ∈ {0, 1}∗ | w = wR}
{wwR | w ∈ {0, 1}∗}
(a) (20 points) Use (some of) the sets above, along with any regular sets you would like, to give
example values for A1, A2, A3, B1, B2 such that A1 and A2 and A3 are each regular, B1 and
B2 are each nonregular, and
A1 ( B1 ( B2 ( A2 ( A3
Recall that X ( Y means that X is a proper subset of Y ; that is, that X ⊆ Y and that
X 6= Y .
For each of your examples of regular sets, clearly define the set and justify (e.g. by citing
an example in the book or by proving it from scratch) why the set is regular and why the
proper subset relations hold.
(b) (10 points) (Graded for fair effort completeness) The Pumping Lemma is useful for proving
that some sets are nonregular. Explain in two or three sentences why it is true (use your
own words; do not quote the book or the videos here) and prove that a set is nonregular
using the pumping lemma for an example set that is not worked out in the book or in the
videos.
1
2. Consider the PDA M over the alphabet {0, 1, 2} whose state diagram is
(a) (5 points) Fill in the full stack contents for each step in the following computation of M on
the input string 12. Then determine whether this computation is a stuck computation, an
accepting computation, or a rejecting computation.
q0 q1 q1 q2 q2 q3
TOP
?
TOP
?
TOP
?
TOP
?
TOP
?
TOP
?
You may hand-draw and scan these traces of the computations. For full credit, include all
stack contents at each step (not just the character, if any, at the top).
Hint: You might find it useful to annotate the steps in the computations with which (if any)
input character is consumed with each transition.
Hint: To get you started, we’ve filled out a computation of M on the input string 01. There
are many other computations of M on this string.
q0 q1 q1 q1
TOP
TOP
$
TOP
$
TOP
X
$
(b) (10 points) Describe an infinite set of strings that is a subset of L(M). For full credit,
precisely define your set and refer to the state diagram to give a general description of what
a successful computation of M on each strings in the set would look like.
(c) (10 points) Consider the language of the context free grammar G = ({S}, {0, 1, 2}, R, S)
where the set of rules R is given by
S → 0S0 | 1S1 | 2
Prove that L(G) 6⊆ L(M) and that L(M) 6⊆ L(G) by giving specific counterexample strings
and explaining why they prove that these subset inclusions do not hold.
Hint: It might be helpful to start by describing, in set builder notation, the set L(G) using
the definition of the CFG.
2
(d) (10 points) (Graded for fair effort completeness) When we introduced PDAs, we used the
stack to give us access to unbounded memory in addition to the finitely many states in the
state diagram. In general, for an arbitrary PDA with an arbitrary string input, is there
any relationship between the length of the input string and the size of the stack during the
computation of the PDA on this input? Define and justify any bounds we can state on the
memory use of the PDA, or explain why there aren’t any.
3. In this question, you’ll practice working with formal general constructions for PDAs and trans-
lating between state diagrams and formal definitions.
Suppose
M = (Q,Σ,Γ, δ, q0, F )
is a PDA. We can define a new PDA N so that L(M) = L(N) and N is guaranteed to have
an empty stack at the end of any accepting computation. Informally, the construction is as
follows: Add three new states q′1, q
′
2, q
′
3 and one new stack symbol #.
• One of the new states q′1 will be the new start state and it has a spontaneous transition to
the old start state q0 which pushes the new stack symbol # to the stack.
• The transitions between the old states are all the same.
• From each of the old accept states, add a spontaneous transition (that doesn’t modify the
stack) to the second new state q′2.
• In this state q′2, pop all old stack symbols from the stack without reading any input.
• When the new stack symbol # is on the top of the stack, transition to the third new state
q′3 and accept.
Assume {q′1, q′2, q′3} ∩Q = ∅ (otherwise, relabel some of the states in Q) and assume that # /∈ Γ
(otherwise, relabel this stack symbol in Γ). Define N to be
N = (Q ∪ {q′1, q′2, q′3},Σ,Γ ∪ {#}, δN , q′1, {q′3})
where δN : Q∪{q′1, q′2, q′3} × Σε × Γε ∪{#} → P(Q∪{q′1, q′2, q′3} × Γε ∪{#}) is defined as
δN( (q, x, y) ) =
{(q0,#)} if q = q′1, x = ε, y = ε
δ( (q, x, y) ) if q ∈ Q, x ∈ Σ, y ∈ Γε
δ( (q, x, y) ) if q ∈ Q, x = ε, y ∈ Γ
δ( (q, x, y) ) if q ∈ Q \ F , x = ε, y = ε
δ( (q, x, y) ) ∪ {(q′2, ε)} if q ∈ F , x = ε, y = ε
{(q′2, ε)} if q = q′2, x = ε, y ∈ Γ
{(q′3, ε)} if q = q′2, x = ε, y = #
∅ otherwise
(a) (10 points) Illustrate this construction by considering the PDA M from the previous ques-
tions
3
and applying the construction above to create the related PDA N and include its state
diagram in your submission. Note: you may include the formal definition of your PDA, but
this is not required.
(b) (20 points) Pick a string of length 5 over the alphabet of the PDA M and use it to demon-
strate the difference in M and in N by
• describing a successful computation of M on this string for which the stack is not empty
at the end of the computation, and
• describing a successful computation of N on this string for which the stack is empty at
the end of the computation.
In your descriptions of these computations, include both the sequence of states visited by the
machine as well as snapshots of the full contents of the stack at each step in the computation.
You may hand-draw and scan these traces of the computations.
Hint: You will need to pick your example string wisely. It must be accepted by M and there
must be a computation of M on your string which ends with a nonempty stack. Not all
choices of length 5 strings work.
(c) (10 points) (Graded for fair effort completeness) In class, we talked about how a language
is recognizable by a PDA if and only if it is generated by a CFG. For an arbitrary PDA
M = (Q,Σ,Γ, δ, q0, F ), let N be the PDA constructed using the general construction above.
Describe how you would translate a CFG that generates L(M) to one that generates L(N).
Include an informal description along with a formal description of how you would translate
the formal definition for the CFG.
Bonus - not for credit; do not hand in Informal descriptions of PDAs are often useful when
working with complex operations. We’ve discussed several shorthands that can be used in
informal descriptions such as “peek at the top of the stack, and if the character is . . . , then
do . . . ”. Give another example of a useful shorthand that can be used when building PDAs,
and explain briefly how you would implement it in the state diagram of a PDA. How would
you translate these constructions to CFGs?
Hint: For ideas of shorthands that are useful, you can look at the informal descriptions of
PDAs in the book in example 2.14 (look back to page 112 for the informal version), example
2.16, and example 2.18.
4