COS3701 Assignment 3 |Theoretical Computer Science III | 2026

UNIVERSITY OF SOUTH AFRICA
School of Computing


⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄


COS3701: Theoretical Computer Science III

Assignment 3 — Semester 1, 2026

⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄




COS3701
Module Code:
Theoretical Computer Science III
Module Name:
Assignment 3
Assignment:
2026
Due Date:
50
Total Marks:




Submitted in partial fulfilment of the requirements for COS3701 — UNISA 2026

,UNISA | COS3701 Assignment 3 – 2026



Question 1: Union of Context-Free Grammars using Theorem 36


Question (Restated)


Let L1 be the grammar generating (a + b)∗ . Let L2 be the grammar generating (aa)∗ b(a +
b)∗ . First provide the grammars generating L1 and L2 respectively. Then apply the applicable
theorem from Chapter 17 (Theorem 36) to determine L1 + L2 .


Step 1: Grammar for L1 = (a + b)∗


The language L1 is the set of all strings over {a, b}, including the empty string ε.

Grammar G1 :



G1 : S1 → aS1 | bS1 | ε


This grammar allows S1 to produce any sequence of a’s and b’s (in any order), followed by ε
to terminate. Therefore G1 generates (a + b)∗ .


Step 2: Grammar for L2 = (aa)∗ b(a + b)∗


The language L2 consists of strings that begin with zero or more occurrences of aa, followed
by exactly one b, followed by any string over {a, b}.

We build this grammar in parts.

Part A – generating (aa)∗ :
A → aaA | ε


Part B – generating (a + b)∗ :

We reuse the same structure as S1 above:


B → aB | bB | ε



Combined grammar G2 :




Page 2 of 20

,UNISA | COS3701 Assignment 3 – 2026




G2 : S2 → AbB

A → aaA | ε

B → aB | bB | ε


Reading this: S2 expands to AbB. The non-terminal A produces zero or more pairs aa, then
the literal b appears in the middle, and B produces any string over {a, b} to the right. There-
fore G2 generates (aa)∗ b(a + b)∗ .


Step 3: Applying Theorem 36 (Union of Context-Free Languages)


⋆ Key Distinction
Theorem 36 (Union): If L1 is generated by grammar G1 = (V1 , Σ, P1 , S1 ) and L2 is
generated by grammar G2 = (V2 , Σ, P2 , S2 ), where V1 ∩V2 = ∅, then L1 +L2 is generated
by the grammar G obtained by adding a new start symbol S and the two productions
S → S1 | S2 , combining all productions of G1 and G2 .


Therefore, the grammar G for L1 + L2 is constructed as follows.

We first ensure variable sets are disjoint. Renaming G2 ’s variables as needed (they are already
disjoint since we used different names), we introduce a new start symbol S and add the pro-
duction S → S1 | S2 .

Grammar G for L1 + L2 :



S → S1 | S2

S1 → aS1 | bS1 | ε

S2 → AbB

A → aaA | ε

B → aB | bB | ε


Explanation of each production:




Page 3 of 20

,UNISA | COS3701 Assignment 3 – 2026


• S → S1 – the derivation follows G1 , producing any word in (a + b)∗ .
• S → S2 – the derivation follows G2 , producing any word in (aa)∗ b(a + b)∗ .
• The final language is L(G) = L1 ∪ L2 = (a + b)∗ ∪ (aa)∗ b(a + b)∗ .

✓ Implementation Insight
Since L1 = (a + b)∗ already contains every string over {a, b}, the union L1 ∪ L2 is simply
(a + b)∗ itself. However, the formal exercise of applying Theorem 36 and construct-
ing the combined grammar is the required demonstration. The grammar above is the
correct formal answer.




Page 4 of 20

, UNISA | COS3701 Assignment 3 – 2026



Question 2: Applying Theorem 42 – Does the Grammar Generate Any Words?


Question (Restated)


Use the Theorem 42 algorithm to determine whether the following grammar generates any
words.



S → XS

X →YX

Y →YY

Y → XX

X→a


Background: Theorem 42 Algorithm


⋆ Key Distinction
Theorem 42 provides an algorithm to determine whether a context-free grammar
(CFG) generates any word at all. The algorithm identifies all productive non-terminals,
i.e., those that can eventually derive at least one terminal string. A grammar generates
a non-empty language if and only if its start symbol is productive.
Algorithm (iterative):

1. Mark any non-terminal A as productive if it has a production A → w where w con-
tains only terminals (or ε).
2. Repeat: mark any non-terminal A as productive if it has a production A → α
where every symbol in α is either a terminal or an already-marked productive non-
terminal.
3. Stop when no new non-terminals can be marked.
4. The grammar generates a word if and only if the start symbol is marked produc-
tive.




Page 5 of 20