UNIVERSITY OF SOUTH AFRICA
School of Computing, College of Science, Engineering and Technology
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS4861: Natural Language Processing
Assignment 3 | Semester 2, 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS4861
Module Code:
Natural Language Processing
Module Name:
ND-RECOGNIZE Search Strategies & Text
Assignment Topic:
Preprocessing Pipeline
3
Assignment Number:
2, 2026
Semester:
Year Module 2026
Due Date:
50
Total Marks:
Submitted in partial fulfilment of the requirements for COS4861, UNISA 2026
, UNISA | COS4861 NLP: ND-RECOGNIZE & Preprocessing Pipeline
Question 1: ND-RECOGNIZE and Non-Deterministic Search Strategies
Chapter 2 of Jurafsky and Martin’s Speech and Language Processing formalises the equiva-
lence between regular expressions and finite-state automata, and shows that a non-deterministic
FSA (NFSA) needs an explicit search procedure, ND-RECOGNIZE, to resolve the multiple tran-
sition choices that determinism would otherwise remove (Jurafsky and Martin, 2024). The
implementation below builds an NFSA for the pattern baa*!, exercises it against the target
string "baaa!", and compares a stack-driven (DFS) agenda against a queue-driven (BFS)
agenda.
1.1 Automaton Representation (5 Marks)
The automaton is represented as a small class, NFSA, wrapping a nested dictionary keyed
first by state and then by input symbol. Each (state, symbol) pair maps to a list of desti-
nation states rather than a single state, which is precisely what makes the automaton non-
deterministic: on symbol a the state q2 can either loop back on itself (to consume another
a, modelling the Kleene star) or, via a separate transition, be reached again after an epsilon
move. Epsilon-moves are stored under the reserved symbol string ’eps’ and consume no
input, which is the second required source of non-determinism.
1 class NFSA :
2 """
3 A Non - deterministic Finite State Automaton .
4
5 transitions : dict mapping
6 state -> { symbol -> [ list of destination states ] }
7 A symbol of ’ eps ’ represents an epsilon - transition ( no input consumed ) .
8 Storing a LIST of destination states per ( state , symbol ) pair is what
9 allows the automaton to be non - deterministic .
10 """
11
12 def __init__ ( self , start_state , accept_states ) :
13 self . start_state = start_state
14 self . accept_states = set ( accept_states )
15 self . transitions = {}
16
17 def add_transition ( self , state , symbol , next_state ) :
18 " " " Registers one edge ; repeated calls with the same ( state , symbol )
19 accumulate a list of destinations , modelling non - determinism . " " "
Page 2 of 15
School of Computing, College of Science, Engineering and Technology
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS4861: Natural Language Processing
Assignment 3 | Semester 2, 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS4861
Module Code:
Natural Language Processing
Module Name:
ND-RECOGNIZE Search Strategies & Text
Assignment Topic:
Preprocessing Pipeline
3
Assignment Number:
2, 2026
Semester:
Year Module 2026
Due Date:
50
Total Marks:
Submitted in partial fulfilment of the requirements for COS4861, UNISA 2026
, UNISA | COS4861 NLP: ND-RECOGNIZE & Preprocessing Pipeline
Question 1: ND-RECOGNIZE and Non-Deterministic Search Strategies
Chapter 2 of Jurafsky and Martin’s Speech and Language Processing formalises the equiva-
lence between regular expressions and finite-state automata, and shows that a non-deterministic
FSA (NFSA) needs an explicit search procedure, ND-RECOGNIZE, to resolve the multiple tran-
sition choices that determinism would otherwise remove (Jurafsky and Martin, 2024). The
implementation below builds an NFSA for the pattern baa*!, exercises it against the target
string "baaa!", and compares a stack-driven (DFS) agenda against a queue-driven (BFS)
agenda.
1.1 Automaton Representation (5 Marks)
The automaton is represented as a small class, NFSA, wrapping a nested dictionary keyed
first by state and then by input symbol. Each (state, symbol) pair maps to a list of desti-
nation states rather than a single state, which is precisely what makes the automaton non-
deterministic: on symbol a the state q2 can either loop back on itself (to consume another
a, modelling the Kleene star) or, via a separate transition, be reached again after an epsilon
move. Epsilon-moves are stored under the reserved symbol string ’eps’ and consume no
input, which is the second required source of non-determinism.
1 class NFSA :
2 """
3 A Non - deterministic Finite State Automaton .
4
5 transitions : dict mapping
6 state -> { symbol -> [ list of destination states ] }
7 A symbol of ’ eps ’ represents an epsilon - transition ( no input consumed ) .
8 Storing a LIST of destination states per ( state , symbol ) pair is what
9 allows the automaton to be non - deterministic .
10 """
11
12 def __init__ ( self , start_state , accept_states ) :
13 self . start_state = start_state
14 self . accept_states = set ( accept_states )
15 self . transitions = {}
16
17 def add_transition ( self , state , symbol , next_state ) :
18 " " " Registers one edge ; repeated calls with the same ( state , symbol )
19 accumulate a list of destinations , modelling non - determinism . " " "
Page 2 of 15
