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

1. $$Q$$ is a finite set called the states,
2. $$Σ$$ is a finite set called the alphabet,
3. $$δ : Q × Σ → Q$$ is the transition function,
4. $$q_0 ∈ Q$$ is the start state, and
5. $$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

$$$δ^* : Q × Σ^* → Q$$$

as follows:

1. For every $$q ∈ Q$$, $$δ^∗(q, ε) = q$$
2. 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

$$$δ^*(q_0, a) ∈ F$$$

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

1. $$Q$$ is a finite set called the states,
2. $$Σ$$ is a finite set called the alphabet,
3. $$δ : Q × Σ → P(Q)$$ is the transition function,
4. $$q_0 ∈ Q$$ is the start state, and
5. $$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

$$$δ^* : Q × Σ^* → P(Q)$$$

as follows:

1. For every $$q ∈ Q$$, $$δ^∗(q, ε) = \{q\}$$
2. 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

$$$δ^*(q_0, a) ∩ F \neq ∅ $$$

and is rejected by $$M$$ otherwise.

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

1. $$Q$$ is a finite set called the states,
2. $$Σ$$ is a finite set called the alphabet,
3. $$δ : Q × Σ_ε → P(Q)$$ is the transition function and $$Σ_ε = Σ ∪ \{ε\}$$
4. $$q_0 ∈ Q$$ is the start state, and
5. $$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

$$$δ^* : Q × Σ^* → P(Q)$$$

as follows:

1. For every $$q ∈ Q$$, $$δ^∗(q, ε) = E(\{q\})$$
2. 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$$,

$$$E(S)$$$

as follows:

1. $$S ⊆ E(S)$$
2. 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$$$