COS4861 Assignment 2 2025 |COMPLETE ANSWERS|

COS4861
Assignment 2 2025

, Assignment 2: Natural Language Processing (NLP)

Question 1: Theory of Automata (40 marks)

1.1 Deterministic Finite State Automaton (DFSA)

A Deterministic Finite State Automaton (DFSA) is a type of finite state machine used in
computer science to recognize patterns or decide whether a given string belongs to a
particular language. The word “deterministic” means that for every state and input
symbol, there is exactly one transition to another state the machine never has to guess
or choose between options.

Key Components of a DFSA:

A DFSA is formally defined as a 5-tuple:
M = (Q, Σ, δ, q₀, F) where:

• Q is a finite set of states

• Σ is a finite input alphabet (symbols the automaton can read)

• δ is the transition function: δ: Q × Σ → Q

• q₀ is the start state (q₀ ∈ Q)

• F is the set of accept (final) states, where F ⊆ Q

How it operates:

The DFSA reads a string symbol by symbol, starting from the initial state (q₀). For each
input symbol, it uses the transition function (δ) to move to a new state. If the machine
ends in an accepting state after reading the full string, the string is accepted. If not, it's
rejected.

Example:

Let’s define a DFSA that accepts strings over the alphabet Σ = {0,1} that end with 01.

Define:

• Q = {q₀, q₁, q₂}