2.2 > a. Use the languages A = {a"b"c"|m, n ≥ 0} and B = {a"b" cm, n ≥ 0} together with Example 2.36 to show that the class of context-free languages. is not closed under intersection. b. Use part (a) and DeMorgan's law (Theorem 0.20) to show that the class of context-free languages is not closed under complementation.

2. [Based on Problem 2.26, page 157 in Sipser's 3rd Edition] Suppose G is a context-free grammar in Chomsky normal form. This exercise will help you prove that for any string w e L(G) of length n 2 1, exactly 2n - 1 steps are required for any derivation of w. To make the proof simple, we define: a variable rule is any rule of the form A BC, where A, B,C are variables, • a terminal rule is any rule of the form A → a, where A is a variable and a is a terminal. Now consider a derivation in G that starts with the start variable and applies apply variable rules s times (may not be consecutive) and applies terminal rules t times, and let r be the string generated by the derivation (z can contain both variables and terminals). (a) Prove that the string r contains t terminals. (b) Prove that the string r contains (1+s – t) variables. (c) Prove that if r E L(G) and |2| = n, then s +t = 2n – 1. %3D

Could you lend a hand with this issue? I'm struggling with it, and it would be immensely helpful if you could guide me through it, offering detailed explanations at each step to help me grasp the solution better.

Question 34 The correct statements are: Decidable languages are closed under union. Decidable languages are closed under intersection. Decidable languages are closed under complement. Semi-decidable languages are closed under complement.