# 计算理论代写｜COMP 330 Assignment 5

本次加拿大代写是一个计算理论的assignment

Question 1[20 points] Consider the two languages below:

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:

Prove that this language is context-free by giving a grammar. However this language is not

deterministic context-free: prove this 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.”

Proving 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 fa; b; cg

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 = fabc; aabg then perm(L) =

fabc; acb; bac; bca; cab; cba; aab; aba; baag. I have given an example where the language L is

finite just for illustrative purposes; the same definition works equally well when L is infinite.

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.

Question 4[10 points] Suppose that we have a finite collection of languages L1; : : : ; Ln, all

defined over the same alphabet, Σ. Suppose that Sn i=1 Li = Σ∗ and that for all i and j we

have i 6= j ) Li \ Lj = ;; i.e. each string is in exactly one language. Suppose that all the

languages are computably enumerable. Show that all the languages are decidable. A brief

answer is all that is required.

Question 5[30 points] For each of the three following assertions give brief arguments indi

cating whether they are true of false.

a. The intersection of two decidable languages is decidable.

b. The intersection of two CE languages is CE.

c. If L is decidable then L∗ is also decidable.

Remember when trying to show that something is decidable you need not worry about

efficiency but your algorithm must terminate. Thus, you cannot say things like \check every

word ….” as this will definitely not terminate on an infinite language.