COS3701 Assignment 2 (COMPLETE ANSWERS) 2025

[TYPE THE COMPANY NAME]




COS3701 Assignment 2
(COMPLETE ANSWERS)
2025
NO PLAGIARISM

[Pick the date]




[Type the abstract of the document here. The abstract is typically a short summary of the contents of
the document. Type the abstract of the document here. The abstract is typically a short summary of
the contents of the document.]

,Exam (elaborations)
COS3701 Assignment 2 (COMPLETE
ANSWERS) 2025
Course

 Theoretical Computer Science III (COS3701)
 Institution
 University Of South Africa (Unisa)
 Book
 Theoretical Computer Science

COS3701 Assignment 2 (COMPLETE ANSWERS) 2025 - DUE 2025; 100%
TRUSTED Complete, trusted solutions and explanations. Ensure your success
with us..



Question 1 10 Find CFGs for all words that do not have the substring aba
over the alphabet Σ = {a b}.

Solution: We want to find a Context-Free Grammar (CFG) for the language
L={w∈{a,b}∗∣w does not have the substring aba}.

Let's break down the possible structures of words that do not contain "aba".

A word that does not contain "aba" can be thought of as a sequence of blocks, where no block is
"aba" and no combination of blocks forms "aba".

Consider the states we can be in when building a string that avoids "aba":

1. Initial state (S): We haven't seen any part of "aba" or have just completed a safe
sequence.
2. Seen 'a' (A): We have just seen an 'a', which could be the start of "aba".
3. Seen 'ab' (AB): We have just seen 'ab', which could be the start of "aba".

Let's define the productions based on these states.

Let S be the start symbol. Let A be a non-terminal representing the state where the last character
read was 'a' (and we haven't formed "aba"). Let B be a non-terminal representing the state where
the last characters read were 'ab' (and we haven't formed "aba").

From the start symbol S:

 We can have an empty string: S→ϵ

,  We can start with 'b': S→bS (we are still in a "safe" state after 'b')
 We can start with 'a': S→aA (we've seen 'a', now in state A)

From state A (last character was 'a'):

 If we see 'a' again: A→aA (we still have 'a' as the last character, no "aba" formed)
 If we see 'b': A→bB (we've seen 'ab', now in state B)
 We can end the string here: A→ϵ (the string ends with 'a', no "aba")

From state B (last characters were 'ab'):

 If we see 'a': This would form "aba", which is not allowed. So, B cannot directly
transition to a state that accepts 'a'. However, this is where it gets tricky for CFGs. A CFG
cannot "reject" a character in the same way a DFA does. Instead, the grammar simply
won't have a production for that sequence.
 If we see 'b': B→bS (we've seen 'abb', which is safe, and we effectively reset to a "safe"
state S because the last 'b' doesn't start "aba")
 We can end the string here: B→ϵ (the string ends with 'ab', no "aba")

Let's refine this approach. Instead of thinking about states in a DFA-like manner, let's consider
the structure of strings that avoid "aba".

A string avoiding "aba" can be:

1. Any string not ending in 'a' or 'ab' that avoids "aba".
2. A string ending in 'a' that avoids "aba".
3. A string ending in 'ab' that avoids "aba".

Let S be the start symbol. Consider the blocks that are "safe": 'b', 'a'. If we see 'ab', the next
character must not be 'a'.

Let's try a different approach, based on the idea that any string that does not contain 'aba' can be
formed by:

 Only 'b's: b∗
 Only 'a's: a∗
 Combinations that avoid 'aba'.

A common technique is to consider what happens if we don't see the forbidden substring.

Let's define non-terminals based on the suffix we've built so far that could be a prefix of 'aba'.

S: Generates all words that do not have 'aba'. S→bS S→aA S→ϵ