[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′
).