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
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
