COS3701 Assignment 3 2025
Unique Number:
Due date: 2025
QUESTION 1
CFG for L₁ = (aa)*
S1 → aaS1 | Ʌ
This can generate zero occurrences of aa or one or more occurrences of aa as required.
CFG for L₂ = (a + b)ab(a + b)
S2 → XabY
X → aX | bX | Ʌ
Y → aY | bY | Ʌ
DISCLAIMER & TERMS OF USE
Educational Aid: These study notes are intended to be used as educational resources and should not be seen as a
replacement for individual research, critical analysis, or professional consultation. Students are encouraged to perform
their own research and seek advice from their instructors or academic advisors for specific assignment guidelines.
Personal Responsibility: While every effort has been made to ensure the accuracy and reliability of the information in
these study notes, the seller does not guarantee the completeness or correctness of all content. The buyer is
responsible for verifying the accuracy of the information and exercising their own judgment when applying it to their
assignments.
Academic Integrity: It is essential for students to maintain academic integrity and follow their institution's policies
regarding plagiarism, citation, and referencing. These study notes should be used as learning tools and sources of
inspiration. Any direct reproduction of the content without proper citation and acknowledgment may be considered
academic misconduct.
Limited Liability: The seller shall not be liable for any direct or indirect damages, losses, or consequences arising from
the use of these notes. This includes, but is not limited to, poor academic performance, penalties, or any other negative
consequences resulting from the application or misuse of the information provided.
, For additional support +27 81 278 3372
QUESTION 1
CFG for L₁ = (aa)*
S1 → aaS1 | Ʌ
This can generate zero occurrences of aa or one or more occurrences of aa as
required.
CFG for L₂ = (a + b)ab(a + b)
S2 → XabY
X → aX | bX | Ʌ
Y → aY | bY | Ʌ
By Theorem 37, CFG for L₁L₂:
S → S1 S2
S1 → aaS1 | Ʌ
S2 → XabY
X → aX | bX | Ʌ
Y → aY | bY | Ʌ
QUESTION 2
Given CFG:
S → AB
A → BC | b
B → CD
C → DA
Unique Number:
Due date: 2025
QUESTION 1
CFG for L₁ = (aa)*
S1 → aaS1 | Ʌ
This can generate zero occurrences of aa or one or more occurrences of aa as required.
CFG for L₂ = (a + b)ab(a + b)
S2 → XabY
X → aX | bX | Ʌ
Y → aY | bY | Ʌ
DISCLAIMER & TERMS OF USE
Educational Aid: These study notes are intended to be used as educational resources and should not be seen as a
replacement for individual research, critical analysis, or professional consultation. Students are encouraged to perform
their own research and seek advice from their instructors or academic advisors for specific assignment guidelines.
Personal Responsibility: While every effort has been made to ensure the accuracy and reliability of the information in
these study notes, the seller does not guarantee the completeness or correctness of all content. The buyer is
responsible for verifying the accuracy of the information and exercising their own judgment when applying it to their
assignments.
Academic Integrity: It is essential for students to maintain academic integrity and follow their institution's policies
regarding plagiarism, citation, and referencing. These study notes should be used as learning tools and sources of
inspiration. Any direct reproduction of the content without proper citation and acknowledgment may be considered
academic misconduct.
Limited Liability: The seller shall not be liable for any direct or indirect damages, losses, or consequences arising from
the use of these notes. This includes, but is not limited to, poor academic performance, penalties, or any other negative
consequences resulting from the application or misuse of the information provided.
, For additional support +27 81 278 3372
QUESTION 1
CFG for L₁ = (aa)*
S1 → aaS1 | Ʌ
This can generate zero occurrences of aa or one or more occurrences of aa as
required.
CFG for L₂ = (a + b)ab(a + b)
S2 → XabY
X → aX | bX | Ʌ
Y → aY | bY | Ʌ
By Theorem 37, CFG for L₁L₂:
S → S1 S2
S1 → aaS1 | Ʌ
S2 → XabY
X → aX | bX | Ʌ
Y → aY | bY | Ʌ
QUESTION 2
Given CFG:
S → AB
A → BC | b
B → CD
C → DA
