# The extended transition function of a DFA

We want to *extend* the usual transition function $\delta \colon Q \times \Sigma \to Q$ in such that a way that it can take in not just single letters but whole *words*. This amounts to lifting $\delta$ to an **extended transition function** $\widehat{\delta} \colon Q \times \Sigma^* \to Q$ that can take in words, and restricts to $\delta$ on words of the form $w = a$ for a single letter $a \in \Sigma$. Diagrammatically, we can represent this as:

Here, $i \colon Q \times \Sigma \to Q \times \Sigma^*$ is the canonical inclusion $i(q,a) = (q,a)$ (noting that $\Sigma \subseteq \Sigma^*$).

Recall that words $w \in \Sigma^*$ are generated inductively as:
1. *Induction base:* $w = \varepsilon$ (empty word)
2. *Induction step:* $w = xa$ for $x \in \Sigma^*$ and $a \in \Sigma$.

Of course we have $|w| = |x| + |a| = |x|+1$.

With this, we can extend $\delta$ as follows:

:::info
Define the **extended transition function** $\widehat{\delta} \colon Q \times \Sigma^* \to Q$ inductively as
$$\widehat{\delta}(q,w) := \begin{cases}
q & \text{if $w = \varepsilon$} \\
\delta(\widehat{\delta}(q,x),a) & \text{if $w = xa$} \\
\end{cases}
$$
:::

:::info
**Example.** Consider the following DFA $\mathcal A = (Q,\Sigma,\delta,q_0,F)$:
Let $w = baba$. We would like to compute $\widehat{\delta}(1,baba)$. We successively find:
1. $\widehat{\delta}(1,\varepsilon) = 1$
2. $\widehat{\delta}(1,b) = \delta(\widehat{\delta}(1,\varepsilon),b) = \delta(1,b) = 1$
3. $\widehat{\delta}(1,ba) = \delta(\widehat{\delta}(1,b),a) = \delta(1,a) = 2$
4. $\widehat{\delta}(1,bab) = \delta(\widehat{\delta}(1,ba),b) = \delta(2,b) = 3$
5. $\widehat{\delta}(1,baba) = \delta(\widehat{\delta}(1,bab),a) = \delta(3,a) = 3$

Thus, in particular $\widehat{\delta}(1,baba) = 3 \in F$ is an accepting state.
:::

The latter observation in particular suggests (which one can indeed formally prove) that the language accepted by a DFA $\mathcal A= (Q,\Sigma,\delta,q_0,F)$ can be formally described as: $L(\mathcal A) = \{w \in \Sigma^* \; | \; \widehat{\delta}(w,q) \in F\}$

Consider the following automata $\mathcal A^{(1)} = (Q^{(1)}, \Sigma, \delta^{(1)}, q_0^{(1)}, F^{(1)})$ and $\mathcal A^{(2)} = (Q^{(2)}, \Sigma, \delta^{(2)}, q_0^{(2)}, F^{(2)})$:

$\mathcal A^{(1)}$:

$\mathcal A^{(2)}$:

:::warning
**Exercise (Extended transition function)**
For $\mathcal A^{(1)}$, compute $\widehat{\delta^{(1)}}(1,abaa)$. For $\mathcal A^{(2)}$, compute $\widehat{\delta^{(2)}}(1,abba)$. Systematically write down all your computation steps.
:::