Definition 1.0.0

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.
Definition 1.0.1

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.
Definition 1.0.2

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 )$$

Definition 1.0.3

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.

Definition 1.0.4

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

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

Definition 1.0.5

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

Definition 1.0.6

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.
Definition 1.0.7

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)\}$$

Definition 1.0.8

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.

Definition 1.0.9

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.
Definition 1.1.0

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)\})$$

Definition 1.1.1

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)$
Definition 1.1.2

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$$