,COS3701 Assignment 2 (COMPLETE
ANSWERS) 2025 – DUE 2025; 100% TRUSTED
Complete, trusted solutions and
explanations.
Question 1 10 Find CFGs for all words that do not
have the substring aba over the alphabet Σ = {a
b}. Question 2 10 Convert the grammar below to
CNF (Hint: Consult the online study material) S aX |
Yb X ZXYZ | a Y b | bY | ᴧ Z a | ᴧ Question 3 15
Build a DPDA that accepts the language L =
{(ab)n(ba)n-2| n > 2}. Question 4 15 Prove that
the language L = {an+1b2n (aa)n b | n > 0} is
non-context free. Use the pumping lemma with
length.
Question 1 [10 Marks]
Find a CFG for all words that do not have the
substring "aba" over the alphabet Σ = {a, b}.
This language is not regular, but context-
free, and we must design a CFG that ensures
"aba" never appears. A method is to
construct states that remember the last 0–2
letters and prevent a transition to a state
where "aba" would be formed.
Let’s define:
, less
CopyEdit
S → aS1 | bS | ε
S1 → aS1 | bS2
S2 → bS | aDead
Dead → Dead a | Dead b
S is the start symbol.
S1 is a state after seeing 'a'.
S2 is a state after seeing 'ab'.
Dead is a trap state triggered if 'aba' is
seen.
We don't allow the derivation that leads to S2
→ aDead unless you want to detect the
invalid case. You may eliminate Dead for
simplicity and use productions only allowing
derivations that avoid "aba".
Question 2 [10 Marks]
Convert the grammar below to CNF (Chomsky
Normal Form)
Original grammar:
less
ANSWERS) 2025 – DUE 2025; 100% TRUSTED
Complete, trusted solutions and
explanations.
Question 1 10 Find CFGs for all words that do not
have the substring aba over the alphabet Σ = {a
b}. Question 2 10 Convert the grammar below to
CNF (Hint: Consult the online study material) S aX |
Yb X ZXYZ | a Y b | bY | ᴧ Z a | ᴧ Question 3 15
Build a DPDA that accepts the language L =
{(ab)n(ba)n-2| n > 2}. Question 4 15 Prove that
the language L = {an+1b2n (aa)n b | n > 0} is
non-context free. Use the pumping lemma with
length.
Question 1 [10 Marks]
Find a CFG for all words that do not have the
substring "aba" over the alphabet Σ = {a, b}.
This language is not regular, but context-
free, and we must design a CFG that ensures
"aba" never appears. A method is to
construct states that remember the last 0–2
letters and prevent a transition to a state
where "aba" would be formed.
Let’s define:
, less
CopyEdit
S → aS1 | bS | ε
S1 → aS1 | bS2
S2 → bS | aDead
Dead → Dead a | Dead b
S is the start symbol.
S1 is a state after seeing 'a'.
S2 is a state after seeing 'ab'.
Dead is a trap state triggered if 'aba' is
seen.
We don't allow the derivation that leads to S2
→ aDead unless you want to detect the
invalid case. You may eliminate Dead for
simplicity and use productions only allowing
derivations that avoid "aba".
Question 2 [10 Marks]
Convert the grammar below to CNF (Chomsky
Normal Form)
Original grammar:
less
