COS3701 Assignment 3 2026 |Theoretical Computer Science III | 2026

UNIVERSITY OF SOUTH AFRICA (UNISA)
School of Computing



⋄



ASSIGNMENT 3
Semester 1 – 2026


⋄




Module Code: COS3701

Module Name: Theoretical Computer Science III

Assignment No.: Assignment 3

Due Date: 2026

Semester: Semester 1, 2026




Submitted in partial fulfilment of the requirements for COS3701
at the University of South Africa.

,UNISA | COS3701 Assignment 3 – 2026



Question 1: Union of Regular Languages via Theorem 36 (Chapter 17)

Question: 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 .


1.1 Grammar for L1 = (a + b)∗


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

A right-linear grammar G1 = (V1 , Σ, R1 , S1 ) generating L1 is:




S1 → aS1 | bS1 | λ



This grammar derives any sequence of a’s and b’s. The production S1 → λ terminates the
derivation, yielding any word in (a + b)∗ .


1.2 Grammar for L2 = (aa)∗ b(a + b)∗


L2 consists of words that begin with an even number (possibly zero) of a’s, followed by ex-
actly one b, followed by any string over {a, b}.

A right-linear grammar G2 = (V2 , Σ, R2 , S2 ) generating L2 is:




S2 → aaS2 | bT

T → aT | bT | λ



Step-by-step justification:


• S2 → aaS2 generates zero or more pairs of a’s, that is the (aa)∗ part.
• S2 → bT consumes the mandatory b and moves to state T .
• T → aT | bT | λ generates any string in (a + b)∗ after the b.




Page 1 of 14

,UNISA | COS3701 Assignment 3 – 2026



1.3 Applying Theorem 36 to Determine L1 + L2


Theorem 36 (Union of Regular Languages): Given two regular grammars G1 and G2 with
start symbols S1 and S2 respectively, the language L(G1 ) ∪ L(G2 ) is generated by a new gram-
mar G whose start symbol S has the additional productions:


S → S1 | S2


together with all productions from G1 and G2 . The non-terminals of G1 and G2 are assumed
to be disjoint.

Applying Theorem 36, the combined grammar G = (V, Σ, R, S) for L1 + L2 is:



V = {S, S1 , S2 , T }, Σ = {a, b}


Productions R:




S → S1 | S2 (new start, union rule)

S1 → aS1 | bS1 | λ (from G1 )

S2 → aaS2 | bT (from G2 )

T → aT | bT | λ (from G2 )



Therefore:
L(G) = L1 + L2 = (a + b)∗ ∪ (aa)∗ b(a + b)∗

Implementation Insight
Since L2 ⊆ L1 (every word in (aa)∗ b(a + b)∗ is also a word over (a + b)∗ ), the union L1 +
L2 = L1 = (a + b)∗ . However, the grammar construction above is still the correct appli-
cation of Theorem 36, and both grammars must be provided explicitly as required.




Page 2 of 14

,UNISA | COS3701 Assignment 3 – 2026



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

Question: Use the Theorem 42 algorithm to determine whether the following grammar gener-
ates any words.



S → XS, X → Y X, Y → Y Y, Y → XX, X→a


2.1 Statement of Theorem 42


Theorem 42 provides an algorithm to determine whether a context-free grammar (CFG) gen-
erates any word. The algorithm identifies all productive non-terminals, that is, those non-
terminals from which at least one terminal string can be derived. A grammar generates some
word if and only if its start symbol is productive.

Algorithm:


1. Mark every non-terminal A as productive if there exists a production A → w where w
consists entirely of terminals (including λ).
2. Repeat: mark A as productive if there exists a production A → α where every symbol in
α is either a terminal or already marked productive.
3. Repeat step 2 until no new non-terminal is marked.
4. If the start symbol S is marked productive, the grammar generates at least one word; oth-
erwise it generates no words.


2.2 Applying the Algorithm


The grammar has non-terminals {S, X, Y } and productions:




S → XS

X →YX

Y →YY

Y → XX

X→a



Page 3 of 14

, UNISA | COS3701 Assignment 3 – 2026



Iteration 1 – Find base productive non-terminals:

Scan all productions for right-hand sides that consist entirely of terminals.


• X → a: the right-hand side is the terminal a. Therefore X is marked productive.
• No production for S or Y has a purely terminal right-hand side at this stage.


After Iteration 1: productive set = {X}.

Iteration 2 – Extend using already-productive non-terminals:

Re-examine all productions, treating X as productive.


• Y → XX: both symbols on the right-hand side are X, and X is productive. Therefore Y
is marked productive.
• S → XS: right-hand side contains X (productive) and S (not yet productive). Cannot
mark S yet.
• Y → Y Y : Y is now productive and Y is productive, so this is consistent but does not add
new non-terminals.
• X → Y X: Y is now productive and X is productive. This does not add any new non-
terminal.


After Iteration 2: productive set = {X, Y }.

Iteration 3 – Extend again:


• S → XS: right-hand side contains X (productive) and S (still not productive). Cannot
mark S.
• No other production adds new productive non-terminals.


After Iteration 3: productive set = {X, Y }. No change; the algorithm terminates.


2.3 Conclusion


The start symbol S is not in the productive set. Every production with S on the left has S
itself on the right (S → XS), creating an infinite recursion with no base case. There is no
production of the form S → w where w is a string containing only terminals or productive
non-terminals without S.



Page 4 of 14