Intuitively, when a DFA processes the empty string, it doesn't do anything: if it started in state [math]q
[/math], then it stays in state [math]q
[/math].
To process the string [math]xa
[/math], the DFA would first process the substring [math]x
[/math], and then take one more step with the character [math]a
[/math] (using the automaton's single step transition function).
This intuition leads to the following definition:
Given an
DFA [math]M
[/math], we define the
extended transition function [math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}:\href{/cs2800/wiki/index.php?title=Q&action=edit&redlink=1}{Q} \href{/cs2800/wiki/index.php/%5Ctimes}{\times} \href{/cs2800/wiki/index.php?title=%5CSigma%5E*&action=edit&redlink=1}{\Sigma^*} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php?title=Q&action=edit&redlink=1}{Q}
[/math] inductively by
[math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}(q,\href{/cs2800/wiki/index.php?title=%5Cvarepsilon&action=edit&redlink=1}{\varepsilon})=q
[/math], and
[math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}(q,xa)=\href{/cs2800/wiki/index.php/%5Cdelta}{\delta}(\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}(q,x),a)
[/math].
