COS3701
Assignment 2
2025 (Answer
Guide) - Due July
2025
QUESTIONS WITH 100%
VERIFIED AND
CERTIFIED ANSWERS.
,1|Page
COS3701 Assignment 2 2025 (Answer Guide) - Due July 2025
QUESTIONS WITH 100% VERIFIED AND CERTIFIED ANSWERS. WRITTEN IN
REQUIRED FORMAT AND WITHIN GIVEN GUIDELINES. IT IS GOOD TO USE AS A
GUIDE AND FOR REFERENCE, NEVER PLAGARIZE. Thank you and success in
your academics.
UNISA, 2025.
Contents
Question 1 10 ............................................................................................................................................ 2
Find CFGs for all words that do not have the substring aba over the alphabet Σ = {a b}. ... 2
Question 2 10 ............................................................................................................................................ 4
Convert the grammar below to CNF (Hint: Consult the online study material) S aX | Yb X
ZXYZ | a Y b | bY | ᴧ Z a | ᴧ ..................................................................................................................... 4
Question 3 15 .......................................................................................................................................... 10
Build a DPDA that accepts the language L = {(ab)n(ba)n-2| n > 2}. .......................................... 10
Question 4 15 .......................................................................................................................................... 13
Prove that the language L = {an+1b2n (aa)n b | n > 0} is non-context free. Use the
pumping lemma with length................................................................................................................ 13
, 2|Page
Question 1 10
Find CFGs for all words that do not have the substring aba over the alphabet Σ =
{a b}.
To find a context-free grammar (CFG) for all words over the alphabet Σ = {a, b} that do
not contain the substring aba, we must construct production rules that:
• Generate any string composed of a’s and b’s, and
• Exclude any substring where a is directly followed by b and then another a.
Step-by-step Strategy
We need to define a grammar where the substring aba can never be formed during
derivation. This means we must carefully track combinations of letters, especially
those involving a followed by b.
To do this, we model the grammar based on states that simulate the last one or two
letters seen this helps us anticipate and prevent generating aba.
CFG Construction
Let:
• S be the start symbol.
• We define a few intermediate symbols:
o S: Start symbol, safe to begin a new string.
o A: We just saw an a.
o B: We just saw a b.
o AB: We just saw ab from here, we must not allow another a.
Now define the grammar rules:
1. S → ε | aA | bB
2. A → aA | bAB | ε
Assignment 2
2025 (Answer
Guide) - Due July
2025
QUESTIONS WITH 100%
VERIFIED AND
CERTIFIED ANSWERS.
,1|Page
COS3701 Assignment 2 2025 (Answer Guide) - Due July 2025
QUESTIONS WITH 100% VERIFIED AND CERTIFIED ANSWERS. WRITTEN IN
REQUIRED FORMAT AND WITHIN GIVEN GUIDELINES. IT IS GOOD TO USE AS A
GUIDE AND FOR REFERENCE, NEVER PLAGARIZE. Thank you and success in
your academics.
UNISA, 2025.
Contents
Question 1 10 ............................................................................................................................................ 2
Find CFGs for all words that do not have the substring aba over the alphabet Σ = {a b}. ... 2
Question 2 10 ............................................................................................................................................ 4
Convert the grammar below to CNF (Hint: Consult the online study material) S aX | Yb X
ZXYZ | a Y b | bY | ᴧ Z a | ᴧ ..................................................................................................................... 4
Question 3 15 .......................................................................................................................................... 10
Build a DPDA that accepts the language L = {(ab)n(ba)n-2| n > 2}. .......................................... 10
Question 4 15 .......................................................................................................................................... 13
Prove that the language L = {an+1b2n (aa)n b | n > 0} is non-context free. Use the
pumping lemma with length................................................................................................................ 13
, 2|Page
Question 1 10
Find CFGs for all words that do not have the substring aba over the alphabet Σ =
{a b}.
To find a context-free grammar (CFG) for all words over the alphabet Σ = {a, b} that do
not contain the substring aba, we must construct production rules that:
• Generate any string composed of a’s and b’s, and
• Exclude any substring where a is directly followed by b and then another a.
Step-by-step Strategy
We need to define a grammar where the substring aba can never be formed during
derivation. This means we must carefully track combinations of letters, especially
those involving a followed by b.
To do this, we model the grammar based on states that simulate the last one or two
letters seen this helps us anticipate and prevent generating aba.
CFG Construction
Let:
• S be the start symbol.
• We define a few intermediate symbols:
o S: Start symbol, safe to begin a new string.
o A: We just saw an a.
o B: We just saw a b.
o AB: We just saw ab from here, we must not allow another a.
Now define the grammar rules:
1. S → ε | aA | bB
2. A → aA | bAB | ε
