COS3701 Assignment 2 (COMPLETE ANSWERS) 2025

,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}.


Let’s construct a grammar that avoids generating
“aba”. We’ll design states to ensure “aba” cannot
be formed.

, Let the variables simulate the end of the last few
characters:


S → start symbol.


A → last character was ‘a’.


B → last character was ‘b’.


AA → last two characters were “aa”.


AB → last two characters were “ab” (be careful
here — adding an a now would create “aba”, which
we must avoid).


BB → last two characters were “bb”, etc.


CFG:


Csharp
Copy code