COS3701
ASSIGNMENT 2
2026
Rewritten study reference
, Please note: Change the words of the Greek letters to the actual Greek letters.
Question 1 (10)
Find a CFG for all words over Sigma = {a, b} that do not contain the substring aba.
Answer
G = (V, Sigma, R, S)
V = {S, A, B}
Sigma = {a, b}
Productions:
S -> bS | aA | epsilon
A -> aA | bB | epsilon
B -> bS | epsilon
How the answer is obtained
Track how close the generated word is to accidentally forming the forbidden pattern aba.
• S is the safe state: no useful part of aba has just been formed.
• A means the last relevant symbol was a, so the word has started to resemble aba.
• B means the ending is ab. From here, an a would create aba, so no rule from B may produce a.
The rule B -> bS | epsilon is the important restriction: after ab, the grammar either stops or adds b. It never
adds a, so aba cannot appear.
Question 2 (10)
Convert the grammar below to Chomsky Normal Form (CNF).
S -> aX | Yb
X -> ZXYZ | a
Y -> b | bY | epsilon
Z -> a | epsilon
Answer
Nullable variables:
Y, Z
After removing epsilon-productions:
S -> aX | Yb | b
X -> ZXYZ | XYZ | ZXZ | ZXY | XZ | XY | ZX | a
Y -> b | bY
Z -> a
Introduce terminal variables:
A -> a
B -> b
Rewritten study reference
ASSIGNMENT 2
2026
Rewritten study reference
, Please note: Change the words of the Greek letters to the actual Greek letters.
Question 1 (10)
Find a CFG for all words over Sigma = {a, b} that do not contain the substring aba.
Answer
G = (V, Sigma, R, S)
V = {S, A, B}
Sigma = {a, b}
Productions:
S -> bS | aA | epsilon
A -> aA | bB | epsilon
B -> bS | epsilon
How the answer is obtained
Track how close the generated word is to accidentally forming the forbidden pattern aba.
• S is the safe state: no useful part of aba has just been formed.
• A means the last relevant symbol was a, so the word has started to resemble aba.
• B means the ending is ab. From here, an a would create aba, so no rule from B may produce a.
The rule B -> bS | epsilon is the important restriction: after ab, the grammar either stops or adds b. It never
adds a, so aba cannot appear.
Question 2 (10)
Convert the grammar below to Chomsky Normal Form (CNF).
S -> aX | Yb
X -> ZXYZ | a
Y -> b | bY | epsilon
Z -> a | epsilon
Answer
Nullable variables:
Y, Z
After removing epsilon-productions:
S -> aX | Yb | b
X -> ZXYZ | XYZ | ZXZ | ZXY | XZ | XY | ZX | a
Y -> b | bY
Z -> a
Introduce terminal variables:
A -> a
B -> b
Rewritten study reference
