COS4861
ASSIGNMENT 2 2025
UNIQUE NO.
DUE DATE: 2025
,Natural Language Processing
COS4861 Assignment 2 2025
Question 1: Theory of Automata (40 marks)
1.1 Define a Deterministic Finite State Automata (DFSA). (10 marks)
A Deterministic Finite State Automaton (DFSA) is a mathematical model used to
recognize patterns within input strings and determine their membership in a particular
language. A DFSA is defined as a 5-tuple (Q, Σ, δ, q₀, F) where:
Q: A finite set of states
Σ: A finite input alphabet
δ: A transition function δ: Q × Σ → Q
q₀: The start state (q₀ ∈ Q)
F: A set of accept (final) states (F ⊆ Q)
Operation: DFSA processes an input string one symbol at a time, transitioning
deterministically from one state to another as defined by δ.
Example: Q = {q0, q1}, Σ = {0,1}, q0 is the start state, F = {q1}, δ defined as:
δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q0
δ(q1, 1) = q1
This DFSA accepts strings that end with '1'.
1.2 Define a Non-Deterministic Finite State Automata (NDFSA). (10 marks)
, An NDFSA is similar to a DFSA but allows multiple transitions for the same input symbol
and even ε-transitions (transitions without consuming input).
An NDFSA is also a 5-tuple (Q, Σ, δ, q₀, F) but with δ: Q × (Σ ∪ {ε}) → 2^Q.
Differences from DFSA:
Multiple transitions per symbol allowed.
Acceptance if any computation path leads to a final state.
Example: Q = {q0, q1}, Σ = {0,1}, q0 is the start, F = {q1}, δ:
δ(q0, 0) = {q0, q1}
δ(q0, 1) = {q0}
δ(q1, 0) = ∅
δ(q1, 1) = {q1}
Accepts strings with at least one 0.
1.3 Prove every NDFSA has an equivalent DFSA. (15 marks)
Use subset construction:
Let NDFSA N:
Q = {A, B}, Σ = {0,1}, q0 = A, F = {B}, δ:
o δ(A,0) = {A,B}, δ(A,1) = {A}
o δ(B,0) = ∅, δ(B,1) = {B}
Construct DFSA:
Start state: {A}
On 0: δ({A},0) = {A,B}
ASSIGNMENT 2 2025
UNIQUE NO.
DUE DATE: 2025
,Natural Language Processing
COS4861 Assignment 2 2025
Question 1: Theory of Automata (40 marks)
1.1 Define a Deterministic Finite State Automata (DFSA). (10 marks)
A Deterministic Finite State Automaton (DFSA) is a mathematical model used to
recognize patterns within input strings and determine their membership in a particular
language. A DFSA is defined as a 5-tuple (Q, Σ, δ, q₀, F) where:
Q: A finite set of states
Σ: A finite input alphabet
δ: A transition function δ: Q × Σ → Q
q₀: The start state (q₀ ∈ Q)
F: A set of accept (final) states (F ⊆ Q)
Operation: DFSA processes an input string one symbol at a time, transitioning
deterministically from one state to another as defined by δ.
Example: Q = {q0, q1}, Σ = {0,1}, q0 is the start state, F = {q1}, δ defined as:
δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q0
δ(q1, 1) = q1
This DFSA accepts strings that end with '1'.
1.2 Define a Non-Deterministic Finite State Automata (NDFSA). (10 marks)
, An NDFSA is similar to a DFSA but allows multiple transitions for the same input symbol
and even ε-transitions (transitions without consuming input).
An NDFSA is also a 5-tuple (Q, Σ, δ, q₀, F) but with δ: Q × (Σ ∪ {ε}) → 2^Q.
Differences from DFSA:
Multiple transitions per symbol allowed.
Acceptance if any computation path leads to a final state.
Example: Q = {q0, q1}, Σ = {0,1}, q0 is the start, F = {q1}, δ:
δ(q0, 0) = {q0, q1}
δ(q0, 1) = {q0}
δ(q1, 0) = ∅
δ(q1, 1) = {q1}
Accepts strings with at least one 0.
1.3 Prove every NDFSA has an equivalent DFSA. (15 marks)
Use subset construction:
Let NDFSA N:
Q = {A, B}, Σ = {0,1}, q0 = A, F = {B}, δ:
o δ(A,0) = {A,B}, δ(A,1) = {A}
o δ(B,0) = ∅, δ(B,1) = {B}
Construct DFSA:
Start state: {A}
On 0: δ({A},0) = {A,B}
