A **deterministic finite automaton (DFA)** $$M$$ is a 5-tuple $$(Q, Σ, δ, q_0, F )$$, where

- $$Q$$ is a finite set called the
**states**, - $$Σ$$ is a finite set called the
**alphabet**, - $$δ : Q × Σ → Q$$ is the
**transition function**, - $$q_0 ∈ Q$$ is the
**start state**, and - $$F ⊆ Q$$ is the set of
**accept states**.

A **state diagram** for DFA $$M = (Q, Σ, δ, q_0, F)$$ is graph defined as follows:

- For each state $$q$$ in $$Q$$ there is a node.
- For each state $$q$$ in $$Q$$ and each input symbol $$a$$ in $$Σ$$, let $$δ(q,a) = p$$. Then the state diagram has an arc (arrow) from node $$q$$ to node $$p$$, labeled $$a$$. If there are several input symbols that cause transitions from $$q$$ to $$p$$, then the state diagram can have one arc, labeled by the list of these symbols.
- There is an arrow into the start state $$q_0$$ which does not originate at any node.
- Nodes corresponding to accepting states (those in $$F$$) are marked by double circle. States not in $$F$$ have a single circle.

Let $$M = (Q, Σ, δ, q_0, F)$$ be a deterministic finite automaton (DFA). We define the **extended transition
function**

as follows:

- For every $$q ∈ Q$$, $$δ^∗(q, ε) = q$$
- For every $$q ∈ Q$$, every $$y ∈ Σ^*$$, and every $$a ∈ Σ$$,

$$$δ^∗(q, ya ) = δ(δ^∗(q, y), a )$$$

Let $$M = (Q, Σ, δ, q_0, F)$$ be a deterministic finite automaton (DFA), and let $$a ∈ Σ^*$$. The string $$a$$ is
**accepted** by $$M$$ if

and is **rejected** by $$M$$ otherwise.

Let $$M$$ be a finite automaton. The language **recognised** by $$M$$ is the set

$$$L(M) = \{a ∈ Σ^∗\ |\ a\ is\ accepted\ by\ M\}$$$

A language $$L ⊆ Σ^*$$ is **regular** if there is a finite automaton $$M$$ such that $$L = L(M)$$.

A **nondeterministic finite automaton (NFA) ** $$M$$ is a 5-tuple $$(Q, Σ, δ, q_0, F)$$, where

- $$Q$$ is a finite set called the
**states**, - $$Σ$$ is a finite set called the
**alphabet**, - $$δ : Q × Σ → P(Q)$$ is the
**transition function**, - $$q_0 ∈ Q$$ is the
**start state**, and - $$F ⊆ Q$$ is the set of
**accept states**.

Let $$M = (Q, Σ, δ, q_0, F)$$ be a nondeterministic finite automaton (NFA). We define the **extended transition
function**

as follows:

- For every $$q ∈ Q$$, $$δ^∗(q, ε) = \{q\}$$
- For every $$q ∈ Q$$, every $$y ∈ Σ^*$$, and every $$a ∈ Σ$$,

$$$δ^∗(q, ya ) = \bigcup \{δ(p,a) \mid p ∈ δ^∗(q, y)\}$$$

Let $$M = (Q, Σ, δ, q_0, F)$$ be a nondeterministic finite automaton (NFA or ε-NFA), and let $$a ∈ Σ^*$$. The string $$a$$ is
**accepted** by $$M$$ if

and is **rejected** by $$M$$ otherwise.

A **nondeterministic finite automaton (ε-NFA)** $$M$$ is a 5-tuple $$(Q, Σ, δ, q_0, F)$$, where

- $$Q$$ is a finite set called the
**states**, - $$Σ$$ is a finite set called the
**alphabet**, - $$δ : Q × Σ_ε → P(Q)$$ is the
**transition function**and $$Σ_ε = Σ ∪ \{ε\}$$ - $$q_0 ∈ Q$$ is the
**start state**, and - $$F ⊆ Q$$ is the set of
**accept states**.

Let $$M = (Q, Σ, δ, q_0, F)$$ be a nondeterministic finite automaton (ε-NFA). We define the **extended transition
function**

as follows:

- For every $$q ∈ Q$$, $$δ^∗(q, ε) = E(\{q\})$$
- For every $$q ∈ Q$$, every $$y ∈ Σ^*$$, and every $$a ∈ Σ$$,

$$$δ^∗(q, ya ) = E(\bigcup \{δ(p,a) \mid p ∈ δ^∗(q, y)\})$$$

Let $$M = (Q, Σ, δ, q_0, F)$$ be a nondeterministic finite automaton (ε-NFA) and $$S ⊆ Q$$.
We define the **ε-closure** of $$S$$,

as follows:

- $$S ⊆ E(S)$$
- For every $$q ∈ E(S)$$, $$δ(q, ε) ⊆ E(S)$$

Let $$A$$ and $$B$$ be sets. Then $$A$$ is a subset of $$B$$, written

$$$A ⊆ B$$$if and only if

$$$\forall x \bullet\text{ If }x \in A, \text{ then }x \in B$$$