Monoids

A monoid is a tuple comprising of a set, an associative binary operator which works on the set, and an identity element. (Think haskell)

$(\mathbb{N}_0, +, 0)$
$(\mathbb{N}, \times, 1)$
$(\sum^*, \circ, \epsilon)$
- Where $\circ$ is string concatenation
- $\epsilon$ is the empty word

Extended Transition Function

A DFA’s transition function expresses change upon input of a symbol. The extended transition function expresses change upon input of a string.

We can define the ETF $\hat{\delta}: Q \times \sum^* \rightarrow Q$ via recursion:

<aside> 🎰 For every $q \in Q$, $\hat{\delta}(q, \epsilon) = q$ For every $q \in Q$ and a word $s \in \sum^$, we can say $s = wa$ for $w \in \sum ^$ and $a \in \sum$. $\hat{\delta}(q, s) = \delta(\hat{\delta}(q, w), a)$

</aside>

Runs

The run of a DFA is simply:

For a string $s = s_1s_2...s_n$, with each $s_i \in \sum$, the run of the DFA on the word $s$ is

$r_0r_1...r_n$ where $r_0 = q_0$ and $r_i = \delta(r_{i-1}, s_i)$