# A dirty little ditty on Finite Automata

Mathematics ·This post builds on the previous post about Formal Languages.

### Some Formal Definitions

#### A Deterministic Finite Automata (DFA) is

- A set \( \mathcal{Q} \) called “states”
- A set \( \Sigma \) called “symbols” or “alphabet”
- A function \( \delta_F:\mathcal{Q}\times\Sigma \to \mathcal{Q} \)
- A designated state \( q_0\in\mathcal{Q} \) called the start point
- A subset \( F\subseteq\mathcal{Q} \) called the “accepting states”

The DFA is then often referred to as the ordered quintuple \( A=(\mathcal{Q},\Sigma,\delta_F,q_0,F) \).

#### Defining how strings act on DFAs.

Given a DFA, \( A=(\mathcal{Q}, \Sigma, \delta, q_0, F) \), a state \( q_i\in\mathcal{Q} \), and a string \( w\in\Sigma^* \), we can define \( \delta(q_i,w) \) like so:

- If \( w \) only has one symbol, we can consider \( w \) to be the symbol and define \( \delta(q_i,w) \) to be the same as if we considered \( w \) as the symbol
- If \( w=xv \), where \( x\in\Sigma \) and \( v\in\Sigma^* \), then \( \delta(q_i, w)=\delta(\delta(q_i,x),v) \)

And in this way, we have defined how DFAs can interpret strings of symbols rather than just single symbols.

#### The language of a DFA

Given a DFA, \( A=(\mathcal{Q}, \Sigma, \delta, q_0, F) \), we can define “the language of \( A \)”, denoted \( L(A) \), as \( {w\in\Sigma^*|\delta(q_0,w)\in F} \).

### Some Examples, Maybe?

#### Example 1:

Let’s construct a DFA that accepts only strings beginning with a 1 that, when interpreted as binary numbers, are multiples of 5. So some examples of strings that would be in \( L(A) \) are 101, 1010, 1111

### Some More Formal Definitions

#### A Nondeterministic Finite Automata (NFA) is

- A set \( \mathcal{Q} \) called “states”
- A set \( \Sigma \) called “symbols”
- A function \( \delta_N:\mathcal{Q}\times\Sigma \to \mathcal{P}\left(\mathcal{Q}\right) \)
- A designated state \( q_0\in\mathcal{Q} \) called the start point
- A subset \( F\subseteq\mathcal{Q} \) called the “accepting states”

The NFA is then often referred to as the ordered quintuple \( A=(\mathcal{Q},\Sigma,\delta_N,q_0,F) \).

#### Defining how strings act on NFAs.

Given an NFA, \( N=(\mathcal{Q}, \Sigma, \delta, q_0, F) \), a collection of states \( \mathcal{S}\subseteq\mathcal{Q} \), and a string \( w\in\Sigma^* \), we can define \( \delta(\mathcal{S},w) \) like so:

- If \( w \) only has one symbol, then we can consider \( w \) to be the symbol and define \( \delta(\mathcal{S},w):=\bigcup\limits_{s\in\mathcal{S}}\delta(s,w) \)
- If \( w=xv \), where \( x\in\Sigma \) and \( v\in\Sigma^* \), then \( \delta(\mathcal{S}, w)=\bigcup\limits_{s\in\mathcal{S}}\delta(\delta(s,x),v) \)

And in this way, we have defined how NFAs can interpret strings of symbols rather than just single symbols.