COS3701 Assignment 2 2025
Unique Number:
Due date: 2025
QUESTION 1
Find CFGs for all words that do not have the substring aba over the alphabet Σ = {a
b}.
CFG Rules
S → aA | bS | ε
A → aA | bAB | ε
AB → aDead | bS
Examples of valid strings:
"", "a", "b", "aa", "ab", "ba", "bb", "aab", "abb", "bab"
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 Rules
S → aA | bS | ε
A → aA | bAB | ε
AB → aDead | bS
CFG for all strings not containing "aba":
1. S → aA | bS | ε
2. A → aA | bAB | ε
3. AB → bS
Explanation:
S: Starting point. From here, you can generate:
o aA if an "a" is read
o bS if a "b" is read
o ε (empty string is allowed)
A: Seen an "a", must be careful not to follow with "ba"
AB: Seen "ab", avoid completing with "a" (which would make "aba")
We avoid generating "aba" by not allowing AB → a... (that rule is excluded).
Examples of valid strings:
"", "a", "b", "aa", "ab", "ba", "bb", "aab", "abb", "bab"
Examples of strings NOT generated:
"aba", "aaba", "baba", "ababa"
Unique Number:
Due date: 2025
QUESTION 1
Find CFGs for all words that do not have the substring aba over the alphabet Σ = {a
b}.
CFG Rules
S → aA | bS | ε
A → aA | bAB | ε
AB → aDead | bS
Examples of valid strings:
"", "a", "b", "aa", "ab", "ba", "bb", "aab", "abb", "bab"
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 Rules
S → aA | bS | ε
A → aA | bAB | ε
AB → aDead | bS
CFG for all strings not containing "aba":
1. S → aA | bS | ε
2. A → aA | bAB | ε
3. AB → bS
Explanation:
S: Starting point. From here, you can generate:
o aA if an "a" is read
o bS if a "b" is read
o ε (empty string is allowed)
A: Seen an "a", must be careful not to follow with "ba"
AB: Seen "ab", avoid completing with "a" (which would make "aba")
We avoid generating "aba" by not allowing AB → a... (that rule is excluded).
Examples of valid strings:
"", "a", "b", "aa", "ab", "ba", "bb", "aab", "abb", "bab"
Examples of strings NOT generated:
"aba", "aaba", "baba", "ababa"
