COM S 331: Theory of Computing, Summer 2021
Homework Assignment 4
Due at 11:59PM, Wednesday, June 9, on Gradescope.
Problem 15 (30 points). Define a context-free grammar that generates the language L =
{anbm |n ≤ 3m}
Solution G = ({S}, {a, b}, {S → Sb | aSb | aaSb | aaaSb | �}, S)
Here we have S as the start variable and the only variable, and Σ = {a, b}. We defined the rules
to always have a’s before b’s (rule Sb have the variable on the left hand side so if any a is to be
derived further then it will be on the left side of b) so that the general form of anbm is preserved.
Each of the rule either consist of 0 a followed by 1 b, 1 a followed by 1 b, 2 a’s followed by 1 b, 3
a’s followed by 1 b, or the empty string (terminal), thus this grammar will always be producing n
number of a’s followed by m number of b’s such that n ≤ 3m or n/3 ≤ m.
Problem 16 (30 points). Let the context-free grammar G = ({S, Y }, {a, b}, R, S), where R:
S → aSb | bY | Y a
Y → bY | aY | �
1. Describe L(G) in set notation form.
Solution L(G) = {x ∈ Σ∗ |x /∈ {anbn |n ∈ N}}. Σ∗ − {anbn |n ∈ N} is also an answer.
Another way to look at this is Y derives Σ∗, so bY = bΣ∗, Y a = Σ∗a, aSb = anbΣ∗bn∪anΣ∗abn,
thus S derives the set {anbΣ∗bn} ∪ {anΣ∗abn} ∪ {bΣ∗} ∪ {Σ∗a} (this is also an answer).
2. Give the Chomsky normal form of G.
Solution By following the procedure introduced in Theorem 2.9, you should get something
like this.
S → AB1 | BY | Y A | b | a
Y → BY | Y A | b | a
B1 → SB
A→ a
B → b
1
Problem 17 (40 points). Give a context-free grammar that generates the languageA = {aibjck | =
j or j = k where i, j, k ∈ N}. Is your grammar ambiguous? Why or why not?
Solution G = (V,Σ, R, S) where V = {S,U, V,X, Y }, Σ = {a, b, c}, S = S, and R is described as
below:
S → U | V
U → aU | X
V → V c | Y
X → bXc | �
Y → aY b | �
There are two possible cases for any string in A: a∗bncn or anbnc∗ where n ∈ N. Variable U is to
generate a∗bncn since U allows repeated starting a with aU and ends with X where X guarantee
some number of b followed by same number of c with bXc. Variable V is to generate anbnc∗ since V
allows repeated ending c with V c and starts with Y where Y guarantee some number of a followed
by same number of b with aY b.
This grammar is ambiguous since a same string can be derived by different derivations, for example
� can be derived by S → U → X → � or S → V → Y → �.
2