CSE 105 Fall 2020
Homework 3
Due date: Tuesday, November 3, 2020 at 11:59pm
Instructions
One member of the group should upload your group submission to Gradescope. During the
submission process, they will be prompted to add the names of the rest of the group members.
All group members’ names and PIDs should be on each page of the submission.
Your homework must be typed. We recommend that you submit early drafts to Gradescope
so that in case of any technical difficulties, at least some of your work is present. You may
update your submission as many times as you’d like up to the deadline.
Your assignments in this class will be evaluated not only on the correctness of your answers,
but on your ability to present your ideas clearly and logically. You should always explain how
you arrived at your conclusions, using mathematically sound reasoning. Whether you use
formal proof techniques or write a more informal argument for why something is true, your
answers should always be well-supported. Your goal should be to convince the reader that
your results and methods are sound.
Reading Sipser Sections 1.4, 2.1, 2.2, 2.3.
Key ConceptsPumping Lemma, Pushdown automata, context-free grammars, context-free
languages, derivations, parse trees, ambiguous grammars, leftmost derivations.
1. (15 points) Consider the language
L = {ai(ba)i | i ≥ 0}
(a) Draw the state diagram of a PDA that recognizes the language L.
(b) Provide the formal definition of a CFG that describes the language L.
(c) Use the pumping lemma to show that this language is not regular.
2. (15 points) Consider the PDA:
Q = {q0, q1, q2, q3, q4}
Σ = {0, 1}
Γ = {$, 0}
δ(q0, ε, ε) = {(q1, $)}
δ(q1, 0, ε) = {(q1, 0)}
δ(q1, 1, 0) = {(q2, ε)}
δ(q2, ε, 0) = {(q3, ε)}
δ(q3, 1, 0) = {(q2, ε)}
δ(q3, ε, $) = {(q4, ε)}
δ(r, a, b) = ∅ otherwise
q = q0
F = {q0, q4}
(a) Draw the state diagram for the PDA.
(b) Describe the language recognized by this PDA using set builder notation.
1
(c) Provide the formal definition of a CFG that describes this language.
3. (15 points) For a language A over the alphabet {0, 1}, let ZeroSW(A) be the set:
ZeroSW(A) = {0nw0n | n ≥ 0 AND w ∈ A}
We will show that the class of languages recognized by PDAs is closed under the operation ZeroSW.
Let M = (Q, {0, 1},Γ, δ, q0, F ) be a PDA that recognizes A.
Consider the construction of a PDA that recognizes ZeroSW(A):
M ′ = (Q ∪ {qa, qb, qc, qd, qe}, {0, 1},Γ ∪ {$,#}, δ′, qa, {qe}).
assuming that qa /∈ Q, qb /∈ Q, qc /∈ Q, qd /∈ Q, qe /∈ Q and $ /∈ Γ,# /∈ Γ. The transition function is
described below:
δ′(qa, ε, ε) = {(qb, $)}
δ′(qb, 0, ε) = {(qb, 0)}
δ′(qb, ε, ε) = {(q0,#)}
δ′(q, x, y) = δ(q, x, y) if q ∈ Q, x ∈ Σε, y ∈ Γε
δ′(q, ε, ε) = δ(q, ε, ε) ∪ {(qc, ε)} if q ∈ F
δ′(qc, ε, x) = {(qc, ε)} if x ∈ Γ
δ′(qc, ε,#) = {(qd, ε)}
δ′(qd, 0, 0) = {(qd, ε)}
δ′(qd, ε, $) = {(qe, ε)}
δ′(r, u, v) = ∅ otherwise
Consider the following PDA: P with Γ = {1}.
a) Describe using set builder notation the language that is recognized by the PDA P given above.
(no justification necessary.)
b) Apply the above construction to the PDA P and draw the result.
c) Describe using set builder notation the language recognized by the result of the construction, i.e.
ZeroSW(L(P )). (No justification necessary.)
d) Describe in your own words the purpose of qc and why it is necessary in the construction.
4. (15 points)
Consider the following CFG:
G = ({S, T, U}, {0, 1}, R, S}), where the set of rules R is
S → UTU
T → 0T1 | ε
U → 1U0 | ε
2
a) List 3 strings of length 6 that are in the language generated by G, and 3 strings of length 6 that
are not in the language generated by G.
b) Describe the language, in set builder notation, generated by G.
c) Is G an ambiguous grammar? Why or why not?
3

欢迎咨询51作业君