COM S 331: Theory of Computing, Summer 2021
Homework Assignment 5
Due at 11:59PM, Wednesday, June 16, on Gradescope.
Problem 18 (40 points). Let Σ = {0, 1} and let B be the set of all strings that contain at least
one 1 in their second half. Namely, B = {uv |u ∈ Σ∗, v = Σ∗1Σ∗, and |u| ≥ |v|}.
(The reason for |u| ≥ |v|: When |uv| is odd, |u| = b|uv|/2c + 1, thus |u| > |v|. When |uv| is even,
|u| = |v|)
a. Give a context-free grammar that generates B.
Solution G = ({S,X, Y },Σ, R, S) and R is defined as below.
S → XSX | Y 1
X → 0 | 1
Y → XY | X
The rule S → XSX guarantee that |u| is at least equal to |v| because X only derives a terminal
symbol, in other words, if there is one symbol on the left hand side, then there is one symbol on
the right hand side. XSX will only reach a terminal when S → Y 1 and Y → X. This guarantees
that there is always a 1 at at least a symbol to the right of the middle symbol.
b. Give the state diagram of a NPDA that recognizes B. (Hint: use � transitions to guess the center
of the string)
Sample strings in B: 11, 0101, 000100, 000010, 01101, 01010
Sample strings not in B: 0, 1, 10, 100 11100, 01100
Solution Let M = (Q,Σ,Γ, δ, q0, F ) be a NPDA such that L(M) = B where Q = {q0, q1, q2, q3, q4},
Γ = Σ ∪ {$}, F = {q3}, and δ will be described with the state diagram below where a ∈ {0, 1}.
q0 q1 q2 q3 q4
ε, ε→ $ ε, ε→ ε
0, ε→ 0
1, ε→ 1
1, a→ ε a, $→ ε
1, a→ ε
0, a→ ε
M will nondeterministically decides u and v. q1 is to keep track of the length of u, and q2 and q3
are for v. If a string has no 1 in it, then it M will never reach q3. If |u| < |v| then M will be in q4,
else M will be in q3 and accept the string.
1
Problem 19 (20 points). Give the state diagram of a NPDA that recognizes the language
L = {anbm |m < n ≤ 2m}
Solution There are different ways to approach NPDA problems, CFG to NPDA, or straight away
coming up with the NPDA, either way works. The CFG for this language is S → aaXb, X →
aXb | aaXb | ε. With this CFG, we can convert it into a equivalent NPDA using Lemma 2.21 from
textbook.
qstart
qloop
qaccept
ε, ε→ $
ε, ε→ S
ε, S → b
ε, $→ ε
ε, ε→ X
ε, ε→ a
ε, ε→ a
ε,X → b
ε, ε→ X
ε, ε→ a
ε, ε→ a
ε, ε→ a
ε,X → ε
a, a→ ε
b, b→ ε
S → aaXb and X → aaXb produce strings that start with 2m a’s and end with m b’s (case
m < n = 2m). X → aXb adds the same number of a’s followed by b’s in between the a’s and b’s
derived from previous rules (case n ≤ 2m).
If you are to just come up with a NPDA, then it would look something like this.
S A B T
ε, ε→ $
a, ε→ a b, a→ ε
ε, $→ ε
b, aa→ ε
b, aa→ ε
2
Where state A is to push all the a’s, state B to pop the a’s, and it will only reach the final state if
and only if upon reading the last b, it will pop all the a’s on the stack, thus it can take the epsilon
transition to pop the $ on the stack. The transition from A to B is to make sure that m is always
less than n. If n = 2m, then it will always pop 2 a’s when it reads 1 b; if n ≤ m, then it will try
to pop an a from the stack while reading b but this transition leads to a trash state (assuming all
missing transitions leads to trash state); if n > 2m, then it cannot get to the final state because it
cannot pop $ since there will still be a’s left on the stack after the last b is read; if m < n < 2m,
then it will take a combination of popping 1 a or 2 a’s upon reading 1 b but still is able to reach
the end of the stack when it finish reading the b’s.
Problem 20 (20 points). A and B are languages. We define A�B = {xy |x ∈ A, y ∈ B, |x| = |y|}.
Prove that if A and B are both regular languages, then A�B is a context-free language.
(Hint: Construct a NPDA for A�B using the machines for A and B.)
Solution Since A and B are both regular, then we know there exist DFA MA and MB such that
L(MA) = A and L(MB) = B. We can then create a NPDA N that will read the input and push
the symbols onto the stack according to the transitions in MA. Once it reaches a final state in MA,
it will nondeterministically choose between continuing the previous step as if it is reading a longer
string from A, or continue reading the input according to the transitions in MB and popping a
symbol from the stack for every symbol it reads. N accepts the string iff it reaches a final state of
MB and the stack becomes empty when reading the last symbol of the input.
Formally, with MA = (QA,ΣA, δA, sA, FA) and MB = (QB,ΣB, δB, sB, FB), we can define this
NPDA as N = (QA ∪QB ∪{s, f},Σ,Γ, δ, s, {f}) where Σ = ΣA ∪ΣB, Γ = Σ∪{$}, and δ is defined
as below. (You can read δ(q, a, b) = p, c as: at state q, reading in some symbol a from the input
and popping some symbol b from the stack, it transitions to state p and writing some symbol c on
to the stack. Assume all undefined transitions go to a trash state.)
δ(s, ε, ε) = (sA, $)
δ(q, a, ε) = (p, a) such that δA(q, a) = p
δ(q, ε, ε) = (sB, ε) for ∀q ∈ FA
δ(q, a, b) = (p, ε) such that δB(q, a) = p
δ(q, ε, $) = (f, ε) for ∀q ∈ FB
N only accepts a string if upon reading the last symbol of the input, it reaches a final state in MB
and pops the last symbol on the stack (not the ’$’ symbol that we added in the setup) since the
only path to reach the final state is by popping the $ symbol on the stack at a final state of MB.
|x| will have to be equal to |y| to reach the final state as all the symbol of x are being pushed onto
the stack and reading each symbol of y pops a symbol from the stack. If there is not such x that
belongs to A, then N will never reach state sB; if there is an x ∈ A but no such y that belongs to
B, then N will never reach any state in FB, thus never reaching the final state f .
3
Problem 21 (20 points). Let B = {wwR ∈ {0, 1}∗ | |wwR|0 = |wwR|1}. In other words, B
contains the set of all palindromes with an equal number of 0’s and 1’s. Prove that B is not a
context-free language using pumping lemma.
Sample strings in B: �, 1001, 0110, 11000011, 00111100
Sample strings not in B: 0, 1, 00, 11, 01, 10, 111, 101, 100, 1100, 0011, 1010, 0101
Solution According to the pumping lemma, if B is context-free, then there must be a pumping
length p where if s is some string in B with length of at least p, then s can be divided into five
pieces, s = uvxyz while satisfying the following conditions.
(i) ∀i ≥ 0, uvixyiz ∈ B
(ii) |vy| > 0
(iii) |vxy| ≤ p
Assume B is regular and p is the pumping length. Let s = 1p0p0p1p, s ∈ B 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 1’s or all 0’s: pumping it up or down will cause |s|0 6= |s|1 and it will not be
in the language B anymore, so condition (i) is violated.
(b) vxy consists of 10 or 01:
– if 10 or 01 occurs in v or y, the string will not be a palindrome after pumping it up or down, so
condition (i) is violated
– if v consists of all 1’s and y consists of all 0’s (or vice versa), then the string will not be a palindrome
after pumping it up or down, so condition (i) is violated
– if one of vy consists of all 1’s and the other is �,or one of vy consists of all 0’s and the other is �,
then it will have the same result as case (a)
Since there is no way that you can divide s into uvxyz such that all the conditions are satisfied, B
is not regular.
4