Reference no: EM133026375

There are 5 questions for credit and one for your spiritual growth.

Question 1: Consider the two languages below:

L₁ = {a^mbⁿc^k d^j | m, n, k,j ≥ 0 and m = n and k = j }

and

L₂ = {a^mbⁿc^k d^j | 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.

Question 2 Consider the language below:

L = {aⁱb^jc^k | i, j, k ≥ 0 and (i ≠ j or j ≠ k)}.

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 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} . 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 Suppose that we have a finite collection of languages L_1......,L_n, all defined over the same alphabet, Σ. Suppose that Uⁿ_i=1 L_i = ∑* and that for all i and j we have i≠j =› L_i ∩ L_j = Φ 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 For each of the three following assertions give brief arguments indicating 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.

Spiritual grovrth Show that over a one-letter alphabet the context-free languages are regular.