---
title: "Formal definition of DFA"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-define-formally"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-define-formally
site: BCT Engineering
---

# Formal definition of DFA

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Chaitra; 2072 Kartik (asked 2 times)
- Video: [How do we formally define a DFA?](https://www.youtube.com/watch?v=Z0e3NopJOZA) — Easy Theory
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-define-formally
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Formally define a DFA.

## Short answer

A deterministic finite automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F) where Q is a finite set of states, Σ an alphabet, δ: Q×Σ→Q the transition function, q₀ the start state, and F⊆Q the accepting states. It accepts a string if the sequence of transitions from q₀ ends in a state in F.

## Answer

A **deterministic finite automaton (DFA)** is a 5-tuple

M = (Q, Σ, δ, q₀, F)

where
- **Q** is a finite, non-empty set of states,
- **Σ** is a finite input alphabet,
- **δ : Q × Σ → Q** is the transition function (exactly one next state for each state and symbol),
- **q₀ ∈ Q** is the start state,
- **F ⊆ Q** is the set of final (accepting) states.

**Extended transition function** δ* : Q × Σ* → Q:
- δ*(q, ε) = q
- δ*(q, wa) = δ(δ*(q, w), a) for w ∈ Σ*, a ∈ Σ

**Language accepted:** L(M) = { w ∈ Σ* : δ*(q₀, w) ∈ F }. A language is regular iff some DFA accepts it.

#### Example
DFA over {0, 1} accepting strings that end in 1: M = ({q0, q1}, {0,1}, δ, q0, {q1}).

| State | 0 | 1 |
|---|---|---|
| → q0 | q0 | q1 |
| *q1 | q0 | q1 |

```text
         0                    1
       ┌───┐                ┌───┐
       │   ▼        1       │   ▼
 ──►   (q0) ─────────────► ((q1))
         ▲                    │
         └──────── 0 ─────────┘
```

(→ marks the start state, * a final state.) For input 011: q0 →0 q0 →1 q1 →1 q1, which is final, so 011 is accepted.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which is the DFA 5-tuple?
   A. (Q, Σ, δ, q0, F)
   B. (Q, Σ, q0, F, L)
   C. (Q, Σ, δ, F, Γ)
   D. (Q, δ, q0, F, Z)
   Answer: A. States, alphabet, transition function, start state, final states. (Key point: 5-tuple)

2. What is the type of δ in a DFA?
   A. δ : Q × Σ → 2^Q
   B. δ : Q × Σ → Q
   C. δ : Σ → Q
   D. δ : Q → Σ
   Answer: B. Exactly one next state for each state and symbol. (Key point: Transition function)

3. When does a DFA accept w?
   A. δ*(q0, w) = q0
   B. δ*(q0, w) is in F
   C. Some prefix of w leads to a dead state
   D. δ*(q0, w) is not in F
   Answer: B. L(M) = {w : δ*(q0, w) ∈ F}. (Key point: Language accepted)

4. How is δ*(q, wa) defined?
   A. δ(δ*(q, w), a)
   B. δ*(q, w) · a
   C. δ(q, a)
   D. δ*(δ(q, a), w)
   Answer: A. Process w first, then apply the last symbol a. (Key point: Extended δ)