[TYPE THE COMPANY NAME]
COS3701 Assignment 3
(COMPLETE ANSWERS)
2025
NO PLAGIARISM
[Pick the date]
[Type the abstract of the document here. The abstract is typically a short summary of the contents of
the document. Type the abstract of the document here. The abstract is typically a short summary of
the contents of the document.]
,Exam (elaborations)
COS3701 Assignment 3 (COMPLETE
ANSWERS) 2025
Course
Theoretical Computer Science III (COS3701)
Institution
University Of South Africa (Unisa)
Book
Theoretical Computer Science
COS3701 Assignment 3 (COMPLETE ANSWERS) 2025 - DUE 2025; 100%
TRUSTED Complete, trusted solutions and explanations.. Ensure your success
with us..
Question 1 [10] Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find
grammars for L1 and L2. Then use Theorem 37 to find L1L2.
Step 1: Understanding the Languages
L₁ = (aa)*
This language contains any number (including zero) of aa repetitions. Examples: ε, aa,
aaaa, aaaaaa, ...
L₂ = (a + b)*ab(a + b)*
This language contains all strings over {a, b} that contain at least one occurrence of the
substring "ab".
Step 2: Define Grammars for L₁ and L₂
Grammar for L₁ = (aa)*
Let’s define a grammar G₁ = (V₁, Σ, R₁, S₁):
V₁ = {S}
Σ = {a}
R₁:
o S → aaS | ε
This generates strings with any number of "aa" blocks.
, Grammar for L₂ = (a + b)*ab(a + b)*
Let’s define a grammar G₂ = (V₂, Σ, R₂, S₂):
V₂ = {S, A, B}
Σ = {a, b}
R₂:
o S → aS | bS | A
o A → aB
o B → bC
o C → aC | bC | ε
Explanation:
S → aS | bS allows any prefix before ab
A → aB and B → bC enforces "ab"
C generates any suffix (a or b)*
Step 3: Use Theorem 37 (Concatenation of Context-Free
Languages)
Theorem 37:
If L₁ and L₂ are context-free languages, then so is their concatenation L₁L₂, and there exists a
context-free grammar for it.
Constructing the Grammar for L₁L₂
Let G₁ = (V₁, Σ, R₁, S₁) and G₂ = (V₂, Σ, R₂, S₂)
Define a new grammar G = (V, Σ, R, S) where:
V = V₁ ∪ V₂ ∪ {S}
S is the new start symbol.
R = R₁ ∪ R₂ ∪ {S → S₁S₂}
So:
Final Grammar G for L₁L₂
COS3701 Assignment 3
(COMPLETE ANSWERS)
2025
NO PLAGIARISM
[Pick the date]
[Type the abstract of the document here. The abstract is typically a short summary of the contents of
the document. Type the abstract of the document here. The abstract is typically a short summary of
the contents of the document.]
,Exam (elaborations)
COS3701 Assignment 3 (COMPLETE
ANSWERS) 2025
Course
Theoretical Computer Science III (COS3701)
Institution
University Of South Africa (Unisa)
Book
Theoretical Computer Science
COS3701 Assignment 3 (COMPLETE ANSWERS) 2025 - DUE 2025; 100%
TRUSTED Complete, trusted solutions and explanations.. Ensure your success
with us..
Question 1 [10] Given that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find
grammars for L1 and L2. Then use Theorem 37 to find L1L2.
Step 1: Understanding the Languages
L₁ = (aa)*
This language contains any number (including zero) of aa repetitions. Examples: ε, aa,
aaaa, aaaaaa, ...
L₂ = (a + b)*ab(a + b)*
This language contains all strings over {a, b} that contain at least one occurrence of the
substring "ab".
Step 2: Define Grammars for L₁ and L₂
Grammar for L₁ = (aa)*
Let’s define a grammar G₁ = (V₁, Σ, R₁, S₁):
V₁ = {S}
Σ = {a}
R₁:
o S → aaS | ε
This generates strings with any number of "aa" blocks.
, Grammar for L₂ = (a + b)*ab(a + b)*
Let’s define a grammar G₂ = (V₂, Σ, R₂, S₂):
V₂ = {S, A, B}
Σ = {a, b}
R₂:
o S → aS | bS | A
o A → aB
o B → bC
o C → aC | bC | ε
Explanation:
S → aS | bS allows any prefix before ab
A → aB and B → bC enforces "ab"
C generates any suffix (a or b)*
Step 3: Use Theorem 37 (Concatenation of Context-Free
Languages)
Theorem 37:
If L₁ and L₂ are context-free languages, then so is their concatenation L₁L₂, and there exists a
context-free grammar for it.
Constructing the Grammar for L₁L₂
Let G₁ = (V₁, Σ, R₁, S₁) and G₂ = (V₂, Σ, R₂, S₂)
Define a new grammar G = (V, Σ, R, S) where:
V = V₁ ∪ V₂ ∪ {S}
S is the new start symbol.
R = R₁ ∪ R₂ ∪ {S → S₁S₂}
So:
Final Grammar G for L₁L₂
