COM S 331: Theory of Computing, Summer 2021
Exam 2
Designated exam time 11:00 am – 12:40 pm(100 min), Thursday, June 17, on Gradescope.
You have 100 minutes to complete and submit this exam. There are three problems, worth 100
points in total. Any problem that you leave blank or indicate clearly that you do not want graded
will receive 20% credit. Every other problem will be graded and receive 0-35 points for problem 1
and 2, 0-30 for problem 3. All answers should be explained, at least briefly.
While taking the exam you MAY
• consult your own notes and the lecture notes;
• consult the textbook and the class lectures;
• contact the instructor or TA with questions about the exam. (We’ll try to answer promptly,
but cannot guarantee that.)
While taking the exam you may NOT
• post questions or any information about the exam (etc on chegg);
• discuss the exam with anyone except the instructor and TA;
• work with anyone else or access any other resources or websites.
1
Problem 1 (35 points). Give a context-free grammar that generates the language L = {aibjci−j |
i, j ∈ N and i ≥ j}
(To help you understand L, here are some sample strings that are in and not in L:
Sample strings in L: �, ab, aabb, aaabbb, ac, aacc, aaaccc, aabc, aaabbc, aaabcc,
Sample strings not in L: a, b, c, aa, aab, aac, aaa, aaab, aaabb, aaabc, aaacc, bac, cab, ababc )
Solution Not sure about you but looking at aibjci−j as an+mbncm makes it easier for my brain. So
the rules of the grammar will be S → aSc | X, X → aXb | ε where X derives anbn and S derives
amXcm.
Problem 2 (35 points). Give the state diagram of a NPDA that recognizes the language
L = {uv ∈ {0, 1}∗ | u 6= vR and |u| = |v|}. In other words, L is the set of all even length
strings that not palindromes.
(To help you understand L, here are some sample strings that are in and not in L:
Sample strings in L: �, 01, 10, 0001, 1000, 0100, 0010, 000001, 000101
Sample strings not in L: 0, 1, 00, 11, 0000, 0110, 1001 )
Solution The idea is to utilize the nondeterministic characteristic of NPDA to guess the middle of
the string, push u into the stack, pop and check if u = vR (or uR = v) while also check if |u| = |v|.
Let the NPDA N where L(N) = L be N = ({S,U, P, P ′, T},Σ,Σ ∪ {$}, δ, S, {T}) and δ is defined
as below (a, b ∈ Σ, a 6= b).
S U P P ′ T
ε, ε→ $
a, ε→ a
ε, ε→ ε a, b→ ε
a, a→ ε Σ,Σ→ ε
ε, $→ ε
State U is used to push the symbols of u onto the stack, the �-transition from U to P is used to
guess the middle of the string. If uR = v, then N will end at state P since the self loop on P is
saying ”current input is some symbol a and top of the stack is a (also popping this symbol off the
stack)”; if uR 6= v, then N will reach state P ′. A string will only reach the final state if uR 6= v and
|u| = |v|.
Problem 3 (30 points). Prove the language L = {aibjck | i, j, k ∈ N and i > j > k} is not
context-free using pumping lemma.
Solution Assume L is regular and p is the pumping length. Let s = ap+2bp+1cp, s ∈ L and |s| ≥ p.
s can be divided into u, v, x, y, z.
Let’s look at all the possible way to divide the string such that |vxy| ≤ p.
(a) vxy consists of all a’s or all b’s: pumping it down will cause i ≤ j or j ≤ k and it will not be in
2
the language L anymore, so condition (i) is violated.
(b) vxy consists of all c’s: pumping it up will cause j ≤ k and it will not be in the language L
anymore, so condition (i) is violated.
(c) vxy consists of ab or bc:
– if ab or bc occurs in v or y, the string will not have be in the form of a∗b∗c∗ after pumping it up,
so condition (i) is violated
– if v consists of all a’s or y consists of all b’s, then pumping it down will be cause i ≤ j or j ≤ k
– if v consists of all b’s or y consists of all c’s, then pumping it up will cause i ≤ j or i ≤ k.
Since there is no way that you can divide s into uvxyz such that all the conditions are satisfied, L
is not regular.
3