COS4861 Assignment 2 2025 (NLP) Due 2025

COS4861
Assignment 2
(NLP) Due 2025

, COS4861

Assignment 2

Due July 2025

Natural Language Processing

QUESTION 1: Theory of Automata (40 Marks)

1.1 Deterministic Finite State Automaton (DFSA)

Definition:

A Deterministic Finite State Automaton (DFSA) is a mathematical model of
computation used to recognize regular languages. It is deterministic because, for each
input symbol, it allows only one possible transition from a given state.

Formal Definition:

A DFSA is a 5-tuple (Q, Σ, δ, q₀, F) where:

 Q is a finite set of states.
 Σ is a finite set of input symbols (alphabet).
 δ: Q × Σ → Q is the transition function.
 q₀ ∈ Q is the start state.
 F ⊆ Q is the set of accept (final) states.

Key Properties:

 Determinism: For every state and input symbol, there is exactly one transition.
 Finite States: The automaton has a limited number of states.
 No epsilon transitions (ε): Every move must consume an input symbol.

Operational Mechanism: