Department of Computer Science & Software Engineering

Comp335 Introduction to Theoretical Computer Science

Winter 2024

Assignment 3. Solutions

1. Give context-free grammars for each of the following languages.

(a) {an bm ∶ n ≠ m − 1}.

Solution: Here n ≠ m − 1 if and only if there are at least as many a’s as b’s, or at least
two more b’s than a’s.

S → A ∣ B0
A → aAb ∣ aA ∣ 
B0 → Bbb
B → aBb ∣ Bb ∣ 

(b) {an bm ck ∶ n + m ≥ k ≥ 0}.

Solution:
S → aSc ∣ aS ∣ B
B → bBc ∣ bB ∣ 

(c) L, where L = {w ∈ {a, b}∗ ∶ w = an bn , n ≥ 0}.

Solution: Note that L = {an bm ∶ n ≠ m} ∪ {xbay ∶ x, y ∈ {a, b}∗ }.

S→N ∣M ∣B
N → aN b ∣ aN ∣ a
M → aM b ∣ M b ∣ b
B → CbaC ∣ ba
C → aC ∣ bC ∣ 

1
2. The following grammar generates L(0∗ 1(0 + 1)∗ ).
S → A1B
A → 0A ∣ 
B → 0B ∣ 1B ∣ 
Give a leftmost and a rightmost derivation of the string

(a) 00101
Solution:
S ⇒lm A1B ⇒lm 0A1B ⇒lm 00A1B ⇒lm 001B ⇒lm 0010B ⇒lm 00101B ⇒lm 00101
S ⇒rm A1B ⇒rm A10B ⇒rm A101B ⇒rm A101 ⇒rm 0A101 ⇒rm 00A101 ⇒rm 00101
(b) 1001
Solution:
S ⇒lm A1B ⇒lm 1B ⇒lm 10B ⇒lm 100B ⇒lm 1001B ⇒lm 1001
S ⇒rm A1B ⇒rm A10B ⇒rm A100B ⇒rm A1001B ⇒rm A1001 ⇒rm 1001
(c) 000111
Solution:
S ⇒lm A1B ⇒lm 0A1B ⇒lm 00A1B ⇒lm 000A1B ⇒lm 0001B ⇒lm 00011B ⇒lm 000111B ⇒lm
000111
S ⇒rm A1B ⇒rm A11B ⇒rm A111B ⇒rm A111 ⇒rm 0A111 ⇒rm 00A111 ⇒rm 000A111 ⇒rm
000111

3. Let G be the CFG defined by productions S → 0S0 ∣ 1S1 ∣  and L = {wwR ∶ w ∈ {0, 1}∗ }. Prove
that L(G) = L.

Solution: We first show that L(G) ⊆ L by an induction on the number of steps needed to
derive S ⇒∗ w.
Basis: One step. Then S ⇒  is the only possible derivation, and  ∈ L.
Inductive hypothesis: If S ⇒∗ w in k steps (denoted S ⇒k w) then w ∈ L.
Inductive step: We use k + 1 steps. The possible k + 1 step derivations are S ⇒ 0S0 ⇒k 0w0
and S ⇒ 1S1 ⇒k 1w1. By the IH w ∈ L and then clearly 0w0 ∈ L and 1w1 ∈ L.

To see that L ⊆ L(G), we show by an induction on ∣w∣ that if w ∈ L then S ⇒∗ w. Note that
all strings in L are of even length.
Basis: ∣w∣ = 0. Then w =  and S ⇒ .
Inductive hypothesis: If ∣w∣ = k then S ⇒∗ w.
Inductive step: ∣w∣ = k + 2. Then w = 0x0 or w = 1x1, where ∣x∣ = k. By the IH S ⇒∗ x.
Then clearly S ⇒ 0S0 ⇒∗ 0x0 and S ⇒ 1S1 ⇒∗ 1x1.

2
4. In each case below, show that the grammar is ambiguous, and find an equivalent unambiguous
grammar.

(a) S → SS ∣ ab ∣ a

Solution:
The grammar is ambiguous because, the string aaba can be obtained by two different
leftmost derivations:
S ⇒ SS ⇒ SSS ⇒ aSS ⇒ aabS ⇒ aaba
S ⇒ SS ⇒ aS ⇒ aSS ⇒ aabS ⇒ aaba
An unambiguous version is: S → Sa ∣ Sab ∣ a ∣ ab

(b) S → ABA, A → aA ∣ , B → bB ∣ 

Solution:
The grammar is ambiguous because the string a has two leftmost derivations:
S ⇒ ABA ⇒ aABA ⇒ aBA ⇒ aA ⇒ a = a
S ⇒ ABA ⇒ BA ⇒ A ⇒ a = a
An unambiguous version is:
S → ABA ∣ AB ∣ BA ∣ A ∣ B ∣ 
A → aA∣a
B → bB∣b

(c) S → aSb ∣ aaSb ∣ 

Solution:
The grammar is ambiguous because, the string aaabb can be obtained by two leftmost
derivations:
S ⇒ aSb ⇒ aaaSbb ⇒ aaabb = aaabb
S ⇒ aaSb ⇒ aaaSbb ⇒ aaabb = aaabb
An unambiguous version is:
S→A∣
A → aAb ∣ B ∣ ab
B → aaBb ∣ aab

3
5. Design a PDA to accept each of the following languages. You may design your PDA to accept
either by final state or empty stack, whichever is more convenient. Give your solution as a
transition diagram, using the notation of the Hopcroft-Motwani-Ullman textbook.

(a) {an x ∶ n ≥ 0, x ∈ {a, b}∗ and ∣x∣ ≤ n}.

Solution:

a, Z0 /aZ0 a, a/
a, a/aa b, a/

start q0 q1
, Z0 /Z0
, a/a

(b) {w ∈ {a, b, c}∗ ∶ na (w) < nb (w) or na (w) < nc (w)}.

Solution:

b, Z0 /bZ0
b, b/bb
b, a/

a, Z0 /aZ0
a, a/aa q1
a, b/

c, Z0 /Z0
, Z0 /Z0 , b/b
c, a/a
c, b/b

start q0 q3

c, Z0 /cZ0
c, c/cc
, Z0 /Z0 , c/c
c, a/

a, Z0 /aZ0
a, a/aa q2
a, b/

b, Z0 /Z0
b, a/a
b, b/b

4
(c) {w ∈ {a, b}∗ ∶ w ≠ xxR for any x ∈ {a, b}∗ }.

Solution: Note that if ∣w∣ is odd, then w ≠ xxR , for any x ∈ {a, b}∗ . Note also that  = R ,
so the empty string is not accepted.

a, Z0 /aZ0
a, a/aa
a, b/ab a, a/
b, Z0 /bZ0 a, b/
b, a/ba a, a/ b, a/
b, b/bb b, b/ b, b/
, a/a a, b/
, b/b b, a/
q1 q2 q3

, Z0 /Z0 , Z0 /Z0

start q0 q4

a, Z0 /Z0
b, Z0 /Z0
a, Z0 /Z0
b, Z0 /Z0

q5 q6

a, Z0 /Z0
b, Z0 /Z0

5
6. Convert the following grammars into Chomsky Normal Form:
S → AB ∣ aB
A → abb ∣ 
(a) B → bbA
C → BC
D → a

Solution:
● First we clean up the grammar in three steps:
i. Eliminate -productions:
As A → , we have that A is a nullable symbol. No other symbols are nullable, so we
remove A →  and replace S → AB ∣ aB with S → B ∣ AB ∣ aB, and replace B → bbA
with B → bb ∣ bbA.

Resulting grammar:

S → B ∣ AB ∣ aB
A → abb
B → bb ∣ bbA
C → BC
D → a

ii. Eliminate unit productions:

The only unit production is S → B and we replace S → B with S → bb ∣ bbA resulting
in grammar

S → bb ∣ bbA ∣ AB ∣ aB
A → abb
B → bb ∣ bbA
C → BC
D → a

iii. Eliminate useless symbols:

C is non-generating so we eliminate C → BC. D is non-reachable so we eliminate

D → a.

Resulting grammar:

S → bb ∣ bbA ∣ AB ∣ aB
A → abb
B → bb ∣ bbA

6
● Arrange that all bodies of length 2 or more consists of only variables:
We introduce variables variables Xa , Xb , and productions Xa → a, Xb → b.

Resulting grammar:

S → Xb Xb ∣ Xb Xb A ∣ AB ∣ Xa B
A → Xa Xb X b
B → Xb Xb ∣ Xb Xb A
Xa → a
Xb → b

● Break bodies of length 3 or more into a cascade of two-variable-bodied productions.

Introduce new variables Y1 , Y2 and Y3 . to split these bodies, yielding the CNF grammar:

S → Xb Xb ∣ Xb Y1 ∣ AB ∣ Xa B
Y1 → Xb A
A → X a Y2
Y2 → X b Xb
B → X b Xb ∣ Xb Y3
Y3 → Xb A
Xa → a
Xb → b

7
 S → A ∣ Ba
(b) A → B
B → S∣a

Solution:
First we clean up the grammar in 3 steps:

i. Eliminate -productions: There are no -productions.

ii. Eliminate unit productions. We calculate the unit pairs and productions:

Pair Productions

(S, S) S → Ba
(S, A)
(S, B) S→a
(A, S) A → Ba
(A, A)
(A, B) A→a
(B, S) B → Ba ∣ a
(B, A)
(B, B) B→a

iii. Eliminate useless symbols. There are no useless symbols.

● Arrange that all bodies of length 2 or more consists of only variables:

We introduce variables variables Xa , Xb , and productions Xa → a, Xb → b.

Resulting grammar:

S → Ba
A → BXa ∣ Xa
B → BXa ∣ Xa
Xa → a
Xb → b

● Break bodies on length 3 or more. No such rules.

The CNF grammar is above. Note that the above grammar is not minimal. A minimal
equivalent grammar would be S → Sa ∣ a. However, finding a minimal equivalent grammar
is in general undecidable, and CNF doesn’t minimize.

8
7. Using the methods in the Hopcroft-Motwani-Ullman text, convert the grammar
G = ({S, A}, {a, b}, {S → aAA, A → aS∣bS∣a}, S})
to a null stack PDA that accepts exactly L(G).

Solution:

Let P = ({q}, {a, b}, {a, b, S, A}, δ, q, S), where

δ(q, , S) = {(q, aAA)}

δ(q, , A) = {(q, aS), (q, bS), (q, a)}
δ(q, a, a) = {(q, )}
δ(q, b, b) = {(q, )}.

8. (a) Convert the null-stack PDA P = ({q}, {a, b}, {A, B, Z0 }, δ, q, Z0 ), where
δ(q, , Z0 ) = {(q, )}
δ(q, a, Z0 ) = {(q, AZ0 )}
δ(q, a, A) = {(q, AA)}
δ(q, b, A) = {(q, )}
δ(q, B, Z0 ) = {(q, BZ0 )}
δ(q, b, B) = {(q, BB)}
δ(q, a, B) = {(q, )}
to a CFG G, such that L(G) = N (P ).

Solution:

This is greatly simplified by the fact that P has only one state. Instead of variables
[qZ0 q], [qAq], [qBq], we can simply use Z0 , A, B. The start symbol is S, and the terminals
are a and b. The productions are are follows:
S → Z0
(q, ) ∈ δ(q, , Z0 ) z→ Z0 → 
(q, AZ0 ) ∈ δ(q, a, Z0 ) z→ Z0 → aAZ0
(q, AA) ∈ δ(q, a, A) z→ A → aAA
(q, ) ∈ δ(q, b, A) z→ A→b
(q, BZ0 ) ∈ δ(q, b, Z0 ) z→ Z0 → bBZ0
(q, BB) ∈ δ(q, b, B) z→ B → bBB
(q, ) ∈ δ(q, a, B) z→ B→a

(b) Show the derivation of string aababb in the resulting grammar.

Solution:

S ⇒ Z0 ⇒ aAZ0 ⇒ aaAAZ0 ⇒ aabAZ0 ⇒ aabaAAZ0 ⇒ aababAZ0 ⇒ aababbZ0 ⇒ aababb