Assignment 5: 11th March 2021
Prakash Panangaden
COMP 330 Winter 2021 McGill University
Due Date: 25th March 2021
There are 5 questions for credit and two for your spiritual growth. The homework is due at
5pm on myCourses.
Question 1[20 points] Consider the two languages below:
and
L1 ={ambnckdj |m,n,k,j≥0andm=nandk=j} L2 ={ambnckdj |m,n,k,j≥0andm=kandn=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.
Question 2[20 points] Consider the language below:
L={aibjck |i,j,k≥0and(i̸=jorj̸=k)}.
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.
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
1
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.
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.
Question 5[20 points] Prove that the complement of the set of palindromes is context-free: this is the set of words {w ∈ Σ∗|w ̸= 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.
Spiritual growth 1[0 points] Show that over a one-letter alphabet the context-free lan- guages are regular.
Spiritual growth 2[0 points] If in Q3 we restricted our alphabet to only two letters then the permutations of a CFL would give a CFL. Prove this.
2