Extended Transition Function

automata-theory computer-science

Definition

Extended Transition Function

The extended transition function ${\delta }^{\ast }:Q\times {\Sigma }^{\ast }\to Q$ describes the state reached by an automaton after processing an entire input string $w\in {\Sigma }^{\ast }$. It is defined recursively over the length of the string:

$${\delta }^{\ast }(q,w)=\{\begin{array}{ll}q& \text{if }w=\epsilon \\ \delta ({\delta }^{\ast }(q,u),a)& \text{if }w=ua\text{ for }u\in {\Sigma }^{\ast },a\in \Sigma \end{array}$$

Intuitively, ${\delta }^{\ast }(q,w)$ is the state the automaton is in after starting in state $q$ and reading all symbols of $w$ sequentially.