Assignment 5 Solutions
Prakash Panangaden
COMP 330 Winter 2021 McGill University
March 27, 2021
Question 1[20 points] Consider the two languages below:
L1 = {ambnckdj | m,n, k, j ≥ 0 and m = n and k = j}
and
L2 = {ambnckdj | m,n, k, j ≥ 0 and m = k and n = j}.
One of these languages is context-free but the other one is not. Identify which is which. For
the context-free language give a context-free grammar and for the other one give a proof
using the pumping lemma that it is not context-free.
Solution The language L1 is context free but L2 is not. Here is a grammar for L1
S → XY | ε X → aXb | ε Y → cY d | ε.
Here is the pumping lemma proof. Suppose that the demon chooses p. I choose s = apbpcpdp.
Consider possible ways of decomposing the string s = uvwxy with |vx| > 0 and |vwx| ≤
p.
Case 1: v or x crosses a block boundary. In this case choosing i = 2 gets the letters out of
order.
Case 2: v lies in the block of a’s. In this case x cannot lie in the block of c’s as this would
violate the condition |vwx| ≤ p. Thus choosing i = 2 will mean that we no longer have equal
lengths for the a and c blocks.
Case 3: v lies in the block of b’s. Then x cannot be in the block of d’s. Thus, once again,
choosing i = 2 will make the b block and the d block have different lengths.
Any other cases are trivial variations. It is pointless to make a special case out of v may be
ε etc.
Question 2[20 points] Consider the language below:
L = {aibjck | i, j, k ≥ 0 and (i 6= j or j 6= k)}.
1
Prove that this language is context-free by giving a grammar but not deterministic context-
free by showing that its complement is not context-free. The grammar can be rather long
to write out fully so it suffices to explain what you are doing and reduce it to similar cases
and then say, “this case is just like what we have done before.” Of course, if you want to
write out all the rules you are free to do so. Some of you might find that easier than writing
explanations. To prove that the complement is not context free can be done by a reduction
argument to a familiar language that is known to be not context free. A direct pumping
lemma proof would be painful.
Solution Here is a grammar for L:
S → XC|AY
these break the language into the union of two languages; A allows one to produce any
number of a’s and C allows one to produce any number of c’s. The rules for X will ensure
that we have unequal number of a’s and b’s while the rules for Y will ensure that we have
unequal number of b’s and c’s.
X → P |Q P → aPb|R Q→ aQb|R′ R→ aR|a R′ → bR′|b
Here P ensures that there are more a’s than b’s while Q ensures that there are more b’s than
a’s; thus both possibilities are taken into account. In each case, P and Q produce equal
number of a’s and b’s and then finally R producess excess a’s and R′ produces excess b’s.
One can write exactly similar rules for Y . The rules for A and C are obvious.
My original solution for this was wrong, I am indebted to Omar Mohammed Wagih Sadek
for pointing out the mistake. This correction was uploaded on the 27th of March.
The complement of this language is a mess but if we take the intersection with the regular
language a∗b∗c∗ we get
L ∩ a∗b∗c∗ = {anbncn|n ≥ 0}.
This language is well known to be non-context-free. The intersection of a CFL and a regular
language is always a CFL, so the fact that L ∩ a∗b∗c∗ is not a CFL means that L is not a
CFL. Thus L cannot be a DCFL since the latter are closed under complementation.
Question 3[20 points] Suppose that we have a language L defined over the alphabet {a, b, c}
and suppose that L is context-free. We define a new language perm(L) to be the set
of all permutations of all words in L. For example, if L = {abc, aab} then perm(L) =
{abc, acb, bac, bca, cab, cba, aab, aba, baa}. Show that perm(L) need not be context-free by
giving an example of a language L that is context-free but where perm(L) is not context-
free. You need not give a pumping lemma proof if your example is just like one we have
seen in class.
Solution: Consider the regular language (abc)∗; this is regular and hence, certainly context-
free. Now in this language we have equal numbers of a’s b’s and c’s. Now when we construct
2
perm(L) we will obtain words of the form anbncn (among lots of other words). If we intersect
perm(L) with a∗b∗c∗ we get our favourite non context-free language
{anbncn|n ≥ 0}.
Question 4[20 points] We have seen in class that the language L1 = {ai+jbj+kck+i|i, j, k ≥ 0}
over the alphabet {a, b, c} is context free. Consider the language
L2 = {ai+jbj+kck+ldi+l|i, j, k, l ≥ 0}
over the alphabet {a, b, c, d}. Is this language also context free? If so give a context-free
grammar for it; if not prove that it is not context-free using the pumping lemma.
Solution:
This language is context-free. We can design a grammar for it along the same lines as we
did in class.
S → aSd|ABC|ε
A→ aAb|ε B → bBc|ε C → cCd|ε
Question 5[20 points] We assume that the alphabet Σ has two or more letters. Prove
that the complement of the set of palindromes is context-free: this is the set of words
{w ∈ Σ∗|w 6= wrev}. You do not have to give a formal proof but you must explain your
answer. A correct answer without an explanation will only get half the marks.
Solution:
We will design a grammar for this language. Here is the grammar:
S → aSa|bSb|aSb|bSa|aTb|bTa
T → aTa|aTb|bTa|bTb|a|b|ε
The idea is that S allows any kind of pairs but when it switches to T , as it must eventually, it
produces a mismatched pair. Thus, at some point the word generated must have a mismatch
when reading from left to right and from right to left; so it cannot be a palindrome.
3