COS4861
Assignment 2
Natural Language Processing
Due 2025
, Question 1: Theory of Automata
1.1 Definition and Explanation of Deterministic Finite State Automata (DFSA)
A Deterministic Finite State Automaton (DFSA) is a mathematical model of computation de-
signed to recognize regular languages. It processes an input string and either accepts or rejects it based
on whether the string belongs to the defined language.
Key Components of a DFSA
A DFSA is formally defined as a 5-tuple (Q, Σ, δ, q0 , F ), where:
• Q: A finite set of states.
• Σ: A finite set of input symbols, known as the alphabet.
• δ: A transition function, δ : Q × Σ → Q, which maps a current state and input symbol to a unique
next state.
• q0 ∈ Q: The initial state.
• F ⊆ Q: A set of accepting (final) states.
Operation of a DFSA
The DFSA starts in the initial state q0 . For each input symbol, the transition function δ determines the
next state. After processing the entire string, if the final state is in F , the string is accepted; otherwise,
it is rejected.
Example
Consider a DFSA that accepts strings over Σ = {0, 1} with an even number of 1s:
• Q = {q0 , q1 }, where q0 represents an even number of 1s and q1 an odd number.
• Σ = {0, 1}.
• δ:
– δ(q0 , 0) = q0 , δ(q0 , 1) = q1 .
– δ(q1 , 0) = q1 , δ(q1 , 1) = q0 .
• q0 : Initial state (even number of 1s).
• F = {q0 }: Accepting state for even number of 1s.
For the input string “101”:
1. Start at q0 .
2. Read 1: δ(q0 , 1) = q1 .
3. Read 0: δ(q1 , 0) = q1 .
4. Read 1: δ(q1 , 1) = q0 .
5. End in q0 ∈ F , so the string is accepted.
This DFSA is deterministic, as each state-input pair has exactly one next state, ensuring predictable
behavior [1].
1
Assignment 2
Natural Language Processing
Due 2025
, Question 1: Theory of Automata
1.1 Definition and Explanation of Deterministic Finite State Automata (DFSA)
A Deterministic Finite State Automaton (DFSA) is a mathematical model of computation de-
signed to recognize regular languages. It processes an input string and either accepts or rejects it based
on whether the string belongs to the defined language.
Key Components of a DFSA
A DFSA is formally defined as a 5-tuple (Q, Σ, δ, q0 , F ), where:
• Q: A finite set of states.
• Σ: A finite set of input symbols, known as the alphabet.
• δ: A transition function, δ : Q × Σ → Q, which maps a current state and input symbol to a unique
next state.
• q0 ∈ Q: The initial state.
• F ⊆ Q: A set of accepting (final) states.
Operation of a DFSA
The DFSA starts in the initial state q0 . For each input symbol, the transition function δ determines the
next state. After processing the entire string, if the final state is in F , the string is accepted; otherwise,
it is rejected.
Example
Consider a DFSA that accepts strings over Σ = {0, 1} with an even number of 1s:
• Q = {q0 , q1 }, where q0 represents an even number of 1s and q1 an odd number.
• Σ = {0, 1}.
• δ:
– δ(q0 , 0) = q0 , δ(q0 , 1) = q1 .
– δ(q1 , 0) = q1 , δ(q1 , 1) = q0 .
• q0 : Initial state (even number of 1s).
• F = {q0 }: Accepting state for even number of 1s.
For the input string “101”:
1. Start at q0 .
2. Read 1: δ(q0 , 1) = q1 .
3. Read 0: δ(q1 , 0) = q1 .
4. Read 1: δ(q1 , 1) = q0 .
5. End in q0 ∈ F , so the string is accepted.
This DFSA is deterministic, as each state-input pair has exactly one next state, ensuring predictable
behavior [1].
1
