Extended Transition Function

The extended transition function is similar to the transition functions found in DFAs and NFAs. In fact, it is the ‘chaining’ of the (normal) transition function.

Definition §

Extended Transition Function ^definition

Let $A$ be an FSA be defined by $(Q,\Sigma ,F,q_0,\delta )$

Then the extended transition function, ${\delta }^{\ast }$, is notated by

$${\delta }^{\ast }:Q\times {\Sigma }^{\ast }\to Q$$

$${\delta }^{\ast }(q,w)=rq\stackrel{w}{\to }r$$

It takes in a state and a string $w$ (not a single character), and outputs the state after processing the entire string. Another notation when starting from the initial state $q_0$ is:

$$q(w)\leftrightarrow {\delta }^{\ast }(q_0,w)$$

That is, $q(w)$ returns the state we would be at if we processed the string $w$ in $A$, starting at $q_0$.

This is the equivalent of repeatedly chaining the standard transition function:

$${\delta }^{\ast }(q_0,101)=\delta (\delta [\delta (q_0,1),0],1)$$

In terms of the state diagram and its computation paths, the extended transition function essentially creates a path of size $|w|$, while the standard transition function is a single edge path.