计算理论代写｜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.