UNIVERSITY OF SOUTH AFRICA (UNISA)
College of Science, Engineering and Technology — School of Computing
⋄
Natural Language Processing
Assignment 3 — 2026
⋄
Module Code: COS4861
Module Name: Natural Language Processing
Assignment No.: Assignment 3
Due Date: Year Module 2026
Semester: 2026
Department: Computer Science
Submitted in partial fulfilment of the requirements for Natural Language Processing (COS4861)
at the University of South Africa.
, UNISA | COS4861 Assignment 3 — 2026
Question 1: Non-Deterministic Recognition of Regular Languages
Recognition in a non-deterministic finite-state automaton (NFSA) is not a single deterministic
walk through the transition graph but a search problem: at every state offering more than
one outgoing transition on the current symbol, or an ε-move, the machine must keep track
of alternatives it has not yet tried, because a wrong choice can dead-end before the tape is
consumed: a non-deterministic FSA is guaranteed to have at least one accepting path for
any string that belongs to its language, but not every path taken through the machine on that
string will reach an accept state (Jurafsky and Martin, 2007:39–40). The ND-RECOGNIZE
algorithm in Jurafsky and Martin (2007) solves this by maintaining an agenda of search-
states and systematically expanding it until the tape is exhausted at an accepting state or the
agenda is empty. The order in which the agenda is popped, last-in-first-out or first-in-first-out,
is what separates a depth-first search from a breadth-first search over the same graph, and
the two strategies explore an identical search space in a different order, at a different total
cost.
1.1 Automaton Representation
The automaton in Figure 2.21 of Jurafsky and Martin recognises the sheep-language pattern
baa+!, meaning the literal character b, followed by exactly one a, followed by one or more
further a characters (via a self-loop), followed by the literal !. This is represented below as a
Python class rather than a bare nested dictionary, because a class lets the transition table,
the alphabet, the start state and the accepting states travel together as one coherent object
that both search strategies can share without duplication.
Non-determinism is captured by mapping every (state, symbol) pair to a list of destination
states rather than a single state, and ε-moves are stored under the reserved symbol None,
which the search engine treats specially: it can be taken without consuming a character from
the tape.
1 from collections import deque , namedtuple
2
3 # A single search - state on the agenda : the automaton node paired with
4 # the tape pointer at the moment that node was reached .
5 SearchState = namedtuple ( " SearchState " , [ " node " , " pointer " ])
6
7 EPSILON = None # reserved symbol for epsilon - moves
8
Page 1 of 13
College of Science, Engineering and Technology — School of Computing
⋄
Natural Language Processing
Assignment 3 — 2026
⋄
Module Code: COS4861
Module Name: Natural Language Processing
Assignment No.: Assignment 3
Due Date: Year Module 2026
Semester: 2026
Department: Computer Science
Submitted in partial fulfilment of the requirements for Natural Language Processing (COS4861)
at the University of South Africa.
, UNISA | COS4861 Assignment 3 — 2026
Question 1: Non-Deterministic Recognition of Regular Languages
Recognition in a non-deterministic finite-state automaton (NFSA) is not a single deterministic
walk through the transition graph but a search problem: at every state offering more than
one outgoing transition on the current symbol, or an ε-move, the machine must keep track
of alternatives it has not yet tried, because a wrong choice can dead-end before the tape is
consumed: a non-deterministic FSA is guaranteed to have at least one accepting path for
any string that belongs to its language, but not every path taken through the machine on that
string will reach an accept state (Jurafsky and Martin, 2007:39–40). The ND-RECOGNIZE
algorithm in Jurafsky and Martin (2007) solves this by maintaining an agenda of search-
states and systematically expanding it until the tape is exhausted at an accepting state or the
agenda is empty. The order in which the agenda is popped, last-in-first-out or first-in-first-out,
is what separates a depth-first search from a breadth-first search over the same graph, and
the two strategies explore an identical search space in a different order, at a different total
cost.
1.1 Automaton Representation
The automaton in Figure 2.21 of Jurafsky and Martin recognises the sheep-language pattern
baa+!, meaning the literal character b, followed by exactly one a, followed by one or more
further a characters (via a self-loop), followed by the literal !. This is represented below as a
Python class rather than a bare nested dictionary, because a class lets the transition table,
the alphabet, the start state and the accepting states travel together as one coherent object
that both search strategies can share without duplication.
Non-determinism is captured by mapping every (state, symbol) pair to a list of destination
states rather than a single state, and ε-moves are stored under the reserved symbol None,
which the search engine treats specially: it can be taken without consuming a character from
the tape.
1 from collections import deque , namedtuple
2
3 # A single search - state on the agenda : the automaton node paired with
4 # the tape pointer at the moment that node was reached .
5 SearchState = namedtuple ( " SearchState " , [ " node " , " pointer " ])
6
7 EPSILON = None # reserved symbol for epsilon - moves
8
Page 1 of 13
