COS4861 Assignment 2 2025

COS4861
ASSIGNMENT 2 2025

UNIQUE NO.
DUE DATE: 2025

, Question 1: Theory of Automata (40 Marks)

Topic: Deterministic Finite State Automata (DFSA) and Non-Deterministic Finite
State Automata (NDFSA)

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 type of machine used in
computer science to process strings (like words or sequences of characters). The word
deterministic means that the machine is very strict – at every step, it knows exactly what
to do based on the current state and the input symbol.

Key Components of DFSA:

1. States – These are like points or places the machine can be in. (E.g., q0, q1,
q2...)
2. Alphabet – A set of symbols that the machine can read (e.g., a, b, c).
3. Transition function – Tells the machine how to move from one state to another.
4. Start state – The state where the machine starts its process.
5. Accept state(s) – If the machine ends here, the input string is considered
accepted.

Example:

Let’s create a DFSA that accepts any string that ends with "ab" using alphabet {a, b}.

 States: q0 (start), q1, q2 (accepting)
 Transitions:
q0 --a--> q1
q1 --b--> q2
Other transitions just loop or reset.