Automata

1 Finite Automata (FA)

States \[ Q = \{q_0, q_1, \dots, q_n\} \] where:
- one state is the initial state $q_\mathrm{init}\in Q$
- one or more states are final states: $Q_\mathrm{final}\subseteq Q$.
Alphabet \[ \Sigma = \{x_1, x_2, \dots, x_m\} \] Each $x\in\Sigma$ is called a symbol.
Transitions with symbols \[ q_1 \overset{x}{\longrightarrow} q_2 \] where:
- $q_1\in Q$ is the source state,
- $q_2\in Q$ is the target state,
- $x$ is the label, a symbol from the alphabet $\Sigma$, or it can be a special symbol $\epsilon\not\in\Sigma$.

Example

$Q = \{q_0, q_1, q_2, q_3\}$
$\Sigma = \{a, b, c\}$
$Q_\mathrm{final} = \{q_0, q_3\}$
$q_\mathrm{init} = q_0$

2 Mathematical Definitions

2.1 Transition function

\[\Delta: Q\times(\Sigma\cup\{\epsilon\})\to 2^Q\]

$Q$: the source state
$\Sigma\cup\{\epsilon\}$: the labels of transitions
$2^Q$: target states for the source state and label. This is the notation for powersets.

About powerset

A set $X$ with $n$ elements have $2^n$ subsets. The set containing all possible subsets of $X$ is called the powerset of $X$, and is often denoted as $2^X$.

Example

$\Delta(0, a) = \{1\}$
$\Delta(0, \epsilon) = \{2\}$
$\Delta(2, c) = \{1, 3\}$
$\Delta(1, b) = \{3\}$
$\Delta(3, b) = \{1\}$
$\Delta(0, b) = \{\}$

2.2 Automaton

Definition: Automaton

An automaton is defined as:

\[ (Q, \Delta, \Sigma, q_\mathrm{init}, Q_\mathrm{final}) \]

Non-deterministic transition function \[ \exists q\in Q, x\in\Sigma.\; |\Delta(q, x)|\geq 2 \]
Deterministic transition function
1. $\forall q\in Q, x\in\Sigma.\; |\Delta(q, x)|\leq 1$
2. $\forall q\in Q, \Delta(q,\epsilon) = \{\}$, i.e. no $\epsilon$-transitions

Definition: Deterministic Finite Automata (DFA)

A DFA is a finite automaton with a deterministic transition function.

Namely, \[ \Delta(q_1, x) = \{q_2\} \]

This allows as to represent the transition function as a partial function: \[ \delta : Q\times\Sigma\to Q : (q_1, x) \mapsto q_2 \]

Definition: non-deterministc finite automaton (NFA)

A NFA is a finite automaton with no restriction on its transition function.

Note:

All DFA are NFA

3 From Transitions to Strings

Let’s define paths in FA, and thus strings that are recognized by FA.

3.1 $\epsilon$-closure of states

$\newcommand{\epsclosure}{{\epsilon}\text{-closure}}$

Definition: epsilon-closure of sets of states

Let $A\subseteq Q$, we define $\epsclosure(A):2^Q\to 2^Q$ as:

If $q\in A$, then $q\in\epsclosure(A)$.
If $q_1\in\epsclosure(A)$, and $q_2\in\Delta(q_1, \epsilon)$, then $q_2\in\epsclosure(A)$.
Nothing else belongs to $\epsclosure(A)$.

Note:

$\epsclosure(A)$ are the states in $Q$ that can be reached by zero or more $\epsilon$-transitions.

Example

Consider the initial state set be: \[A = \{1, 3\}\] By following the $\epsilon$ transitions, we obtain: \[ \epsclosure(A) = \{1, 2, 4, 3, 5\} \]

3.2 Extending transitions over $\epsilon$: $\Delta^\epsilon$

The extended transition describes the states reachable from a state via a symbol $x$ and zero or more epsilon transitions.

Definition: Extended transition

\[ \Delta^\epsilon:Q\times\Sigma\to 2^Q: (q, x)\mapsto \epsclosure(\Delta(\epsclosure(\{q\}), x)) \]

See illustration below.

$\epsclosure(\{q\}) = \{q, 1\}$
$\Delta(\{q, 1\}, x) = \{2, 3, 4\}$
$\epsclosure(\{2, 3, 4\}) = \{2, 3, 4, 5\}$

3.3 Extending transitions over strings: $\Delta^*$

We now extend $\Delta^*$ further by reaching states over multiple symbols.

Strings

Let $\Sigma$ be the alphabet, and $\Sigma^*$ be the set of all finite strings made up by symbols in $\Sigma$.

The empty string is denoted by $\epsilon$.

What are the states reachable from $q$ via a string $s\in\Sigma^*$? This is computed by the extended transition function:

Extended transition

Denote $s=x_1x_2\dots x_L$.

\[ \Delta^*:Q\times\Sigma^*\to 2^Q \]

defined as,

$\Delta^*(q,\epsilon) = \epsclosure(\{q\})$.
$\Delta^*(q,x_1x_2\dots x_L) = \Delta^\epsilon(\Delta^*(x_1x_2\dots x_{L-1})), x_L)$

3.4 Acceptance of strings

Consider a NFA with transition $\Delta^*$. A string $s\in\Sigma^*$ is accepted by NFA if a final state can be reached by $s$ from the initial state.

\[ s\ \text{accepted\ by}\ \mathbf{NFA} \iff \Delta^*(q_\mathrm{init}, s)\cap Q_\mathrm{final}\not=\emptyset \]

Q: What are the strings accepted by this FA?

A: all binary strings as defined by the regex: [0-1][0-1]*.

4 Languages

Definition: languages

A language is a subset of $\Sigma^*$.

\[ L \subseteq \Sigma^* \]

4.1 Languages of FA

Definition: languages of FA

Given a FA, its language $L(\mathbf{FA})$ is all the strings in $\Sigma^*$ that are accepted by FA.

Definition: expressiveness of NFA and DFA

All languages that can be defined by NFA are defined as: \[ \mathcal{L}_\mathbf{NFA} = \{L\subseteq\Sigma^* : \exists\mathbf{NFA}. L = L(\mathbf{NFA})\} \]

Similarly, all languages that can be defined by DFA are defined as: \[ \mathcal{L}_\mathbf{DFA} = \{L\subseteq\Sigma^* : \exists\mathbf{DFA}. L = L(\mathbf{DFA})\} \]

By definition, we know that $\mathbf{DFA}\subseteq\mathbf{NFA}$, thus, it is trivial that: \[ \mathcal{L}_\mathbf{DFA} \subseteq \mathcal{L}_\mathbf{NFA} \]

A rather surprising answer is YES.

Theorem

\[ \mathcal{L}_\mathbf{NFA} \subseteq \mathcal{L}_\mathbf{DFA} \]

4.2 Powerset construction of DFA

Objective:

Given a NFA defined by $(Q, \Delta, \Sigma, q_0, Q_F)$. Want to construct a DFA \[ \mathbf{DFA} = (\hat{Q}, \delta, \Sigma, \hat{q}_0, \hat{Q}_F) \]

Construction

$\hat Q = 2^Q$: each DFA-state is a subset of the NFA-states.
$\hat q_0 = \epsclosure(\{q_0\})$
$\hat Q_F = \{\hat q\in\hat Q: \hat q\cap Q_F \not=\emptyset\}$
$\delta:\hat Q\times\Sigma\to\hat Q$ is defined as:

$\delta(\hat q, x) = \Delta^*(\hat q, x)$

Example

Consider the following NFA:

$Q = \{1, 2, 3, 4\}$
$\hat Q = \{1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134, 234, 1234\}$

Note: not all $\hat Q$ will be reachable in the final DFA.
$\hat q_0 = 1$

We can construct $\delta: \hat Q\times\Sigma$ as a table.

$\hat Q$	$a$	$b
1	$\Delta^*(1, a) = 23$	$\Delta^*(1, b) = \emptyset$ (not reachable)
23	$\Delta^*(23,a) = \emptyset$	$^*(23, b) = 24
24 (final state)	$\Delta^*(24,a) = \emptyset$	$^*(24, b) = 24

The final DFA transition is shown below:

\(\hat Q\)	\(a\)	$b
1	\(\Delta^*(1, a) = 23\)	\(\Delta^*(1, b) = \emptyset\) (not reachable)
23	\(\Delta^*(23,a) = \emptyset\)	$^*(23, b) = 24
24 (final state)	\(\Delta^*(24,a) = \emptyset\)	$^*(24, b) = 24

Automata

1 Finite Automata (FA)

2 Mathematical Definitions

2.1 Transition function

2.2 Automaton

3 From Transitions to Strings

3.1 \(\epsilon\)-closure of states

3.2 Extending transitions over \(\epsilon\): \(\Delta^\epsilon\)

3.3 Extending transitions over strings: \(\Delta^*\)

3.4 Acceptance of strings

4 Languages

4.1 Languages of FA

4.2 Powerset construction of DFA