COS4861 Assignment 2 (COMPLETE ANSWERS) Semester 1 2025 – DUE 2025; 100% Trusted solution and explanation

,COS4861 Assignment 2 (COMPLETE ANSWERS) Semester
1 2025 – DUE 2025; 100% Trusted solution and
explanation

Question 1; Theory of Automata (40 marks)
Topic: Deterministic Finite State Automata (DFSA) and
Non-Deterministic Finite State Automata (NDaFSA)
1.1 Define a Deterministic Finite State Automata (DFSA).
Explain its key components and how it operates with an
example. (10 marks)



A Deterministic Finite State Automaton (DFSA) is a
theoretical model of computation used in automata theory to
recognize regular languages. It is called deterministic because,
for each 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:
DFSA = (Q, Σ, δ, q₀, F) where:
 Q is a finite set of states.
 Σ is a finite input alphabet (set of symbols).
 δ is the transition function: δ: Q × Σ → Q.
 q₀ ∈ Q is the initial/start state.
 F ⊆ Q is the set of accept/final states.

, Operation:

 The automaton starts at the initial state q₀.
 It reads an input string symbol-by-symbol.
 For each symbol, it follows the transition function δ to the
next state.
 If the automaton ends in an accept state (∈ F) after
processing the input string, the string is accepted;
otherwise, it is rejected.


Example:

Let’s design a DFSA to accept all binary strings that end with
01.
Alphabet (Σ): {0, 1}
States (Q): {q₀, q₁, q₂}
 q₀: Start state
 q₁: After reading 0
 q₂: After reading 01 (accept state)
Accept State: F = {q₂}
Transition Function (δ):
 δ(q₀, 0) = q₁
 δ(q₀, 1) = q₀
 δ(q₁, 0) = q₁
 δ(q₁, 1) = q₂
 δ(q₂, 0) = q₁
 δ(q₂, 1) = q₀