COS4861
Assignment 2
2025
, Question 1.1: Definition of Deterministic Finite State Automaton (DFSA)
[10 Marks]
A Deterministic Finite State Automaton (DFSA) is a fundamental computational model
used to determine whether a given string belongs to a particular regular language. It
functions by processing an input string symbol by symbol, following well-defined
transitions between states.
A DFSA is formally described as a 5-tuple:
Q: A finite set of states
Σ: A finite input alphabet
δ: A transition function defined as δ: Q × Σ → Q
q₀: The start state (an element of Q)
F: A set of accept states (F is a subset of Q)
In a DFSA, every state and input symbol has exactly one defined transition (i.e., it is
deterministic).
Example:
Let the DFSA be defined as M = (Q, Σ, δ, q₀, F), where:
Q = {q₀, q₁}
Σ = {0, 1}
q₀ is the start state
F = {q₁} (final state)
δ is defined as:
o δ(q₀, 0) = q₀
o δ(q₀, 1) = q₁
o δ(q₁, 0) = q₀
Assignment 2
2025
, Question 1.1: Definition of Deterministic Finite State Automaton (DFSA)
[10 Marks]
A Deterministic Finite State Automaton (DFSA) is a fundamental computational model
used to determine whether a given string belongs to a particular regular language. It
functions by processing an input string symbol by symbol, following well-defined
transitions between states.
A DFSA is formally described as a 5-tuple:
Q: A finite set of states
Σ: A finite input alphabet
δ: A transition function defined as δ: Q × Σ → Q
q₀: The start state (an element of Q)
F: A set of accept states (F is a subset of Q)
In a DFSA, every state and input symbol has exactly one defined transition (i.e., it is
deterministic).
Example:
Let the DFSA be defined as M = (Q, Σ, δ, q₀, F), where:
Q = {q₀, q₁}
Σ = {0, 1}
q₀ is the start state
F = {q₁} (final state)
δ is defined as:
o δ(q₀, 0) = q₀
o δ(q₀, 1) = q₁
o δ(q₁, 0) = q₀
