COS3761 Assignment 2 Due July 2025

COS3761
Assignment 2
Due July 2025

, COS3701

Assignment 2

Theoretical Computer Science III – University of South Africa

Due: July 2025

Question 1 (10 Marks):

Find CFGs for all words that do not have the substring "aba" over the alphabet .

Answer:

We are asked to construct a context-free grammar (CFG) that generates all strings over
which do not contain the substring "aba".

We define a grammar that keeps track of the last two characters generated to avoid
forming "aba".

Let:

 be the start symbol
 The grammar must ensure that at no point the substring "aba" appears

We define the following non-terminals:

 : start state, no restriction
 : last character was 'a'
 : last character was 'b'
 : last two characters were 'aa'
 : last two characters were 'ab'
 : last two characters were 'ba'
 : last two characters were 'bb'