SOLVED COMP 335 Introduction to Theoretical Computer Science Assignment 4

  1. [20 Points] For each of the following languages,give a context-free grramar (CFG). (a) (5 Points) La = {a n b m : m, n ≥ 0 and 2n ≤ m ≤ 3n} (b) (5 Points) Lb = {a n b mc k : k = 2m + n} (c) (5 Points) Lc = {a n b mc k : n = m or m ≤ k} (d) (5 Points) Ld = {w ∈ {a, b} ∗ : w ̸= xx, for any x ∈ {a, b} ∗}. 2. [10 Points] Consider the language L = {a n+1b n : n ≥ 0}. (a) (5 points) Describe in English the complement L of L. Your description should specify the types of strings that are in L. That is, it is not acceptable to say L includes every string over {a, b} that is not in L, which is obviously true. (b) (5 points) Give a CFG for L. 3. [15 Points] Let G be the following CFG in which S is the start variable: S → AB | aB A → aab | λ B → bbA (a) (5 Points) Using the procedure discussed in the class, convert G into an equivalent grammar in Chomsky Normal Form (CNF). (b) (5 Points) Find an equivalent grammar to G in Greibach Normal Form (GNF). (c) (5 Points) Suppose we modify the original grammar G as follows: remove the λ-production A → λ and instead add the unit producion A → A. Let us call the resulting grammar as G′ . Convert G′ into CNF, and simplify, if possible. Also describe in English the language L(G′ ).