COS4861 EXAM PACK 2026 – QUESTION & ANSWERS

lOMoARcPSD| 54878315




COS4861/0/2025
Natural Language Processing (NLP)
Total Marks: 100

Primary Lecturer: Dr M.Sibiya




Question 1: Theory of Automata (40 marks)
Topic: Deterministic Finite State Automata (DFSA) and Non-Deterministic Finite State
Automata (NDFSA)

1.1 Define a Deterministic Finite State Automata (DFSA). Explain its key components
and how it operates with an example. (10 marks)

1.2 Define a Non-Deterministic Finite State Automata (NDFSA). Explain its key
components and how it differs from DFSA with an example. (10 marks)

1.3 Prove that for every NDFSA, there exists an equivalent DFSA that recognizes the same
language. Provide a step-by-step example where you convert a given NDFSA into a DFSA.
(15 marks)

1.4 Discuss the significance of DFSA and NDFSA in the context of Natural Language
Processing (NLP). Provide examples of how these automata models might be used in NLP
tasks. (5 marks)




Question 2: Practical Project on NLP Data Preprocessing (60 marks)
Topic: Data Preprocessing Techniques in NLP

2.1 Create a block diagram to represent the workflow of an NLP data preprocessing pipeline.
The pipeline should include the following stages: Tokenization, Stopwords Removal,
Stemming, and Lemmatization. (10 marks)

2.2 Select a small text dataset (e.g., a paragraph or set of sentences). Apply each of the
following preprocessing techniques on this dataset:

• Tokenization: Split the text into tokens (words).
• Stopwords Removal: Remove common stopwords from the tokenized text.
• Stemming: Apply a stemming algorithm (e.g., Porter Stemmer) to reduce words to
their base forms.
• Lemmatization: Apply lemmatization to reduce words to their dictionary form. (25
marks)

2.3 Explain each step of the preprocessing techniques applied in 2.2. Provide insights into
the significance of each technique and how it impacts the final dataset. (15 marks)

, lOMoARcPSD| 54878315




COS4861/0/2025
3

2.4 Conclusion: Write a conclusion summarizing the effects of the preprocessing steps on
the text data. Discuss how these techniques help in improving the performance of NLP
models. (10 marks)


4

,Question 1: Theory of Automata (40 marks)
Topic: Deterministic Finite State Automata (DFSA) and Non-Deterministic Finite State
Automata (NDFSA)




1.1 Deterministic Finite State Automata (DFSA) (10 marks)
Definition:
A Deterministic Finite State Automaton (DFSA) is a mathematical model of computation
used to recognize patterns or languages. It is called deterministic because for every state
and input symbol, there is exactly one transition to a next state.

Key components of a DFSA:
A DFSA is formally defined as a 5-tuple:

M = (Q, Σ, δ, q0, F )
Where:

1. Q – A finite set of states
2. Σ – A finite input alphabet
3. δ – A transition function:

δ : Q×Σ→ Q
4. q₀ – The initial (start) state, where computation begins

, 5. F – A set of final (accepting) states

How a DFSA operates:

The automaton starts in the initial state q0.
It reads the input string one symbol at a time.
For each symbol, it moves to exactly one next state as defined by the transition
function.
After reading the entire input, the string is accepted if the automaton ends in a final
state; otherwise, it is rejected.

Example:

Consider a DFSA that accepts all strings over {0, 1} that end with 1.

States: Q = {q0, q1}
Alphabet: Σ = {0, 1}
Start state: q0
Accepting state: F = {q1}

Transitions:

From q0:
On 0 → stay in q0
On 1 → move to q1
From q1:
On 0 → move to q0
On 1 → stay in q1

This DFSA deterministically decides whether a string ends with 1 .




1.2 Non-Deterministic Finite State Automata (NDFSA) (10 marks)
Definition:
A Non-Deterministic Finite State Automaton (NDFSA) is a finite automaton where, for a
given state and input symbol, the machine may move to zero, one, or multiple states. It
may also include ε-transitions (transitions without consuming input).

Key components of an NDFSA:
An NDFSA is also defined as a 5-tuple:

M = (Q, Σ, δ, q0, F )