The extended transition function [math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}_M}
[/math] of an automaton [math]M
[/math] tells us what state [math]M
[/math] ends up in after processing an entire string of characters. In fact, the definition of [math]\href{/cs2800/wiki/index.php/Delta_hat}{delta hat}\hat{\delta}]]
[/math] is what tells us what we mean when we say "process a string".
[math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}
[/math] is similar to [math]\href{/cs2800/wiki/index.php/%5Cdelta}{\delta}
[/math] but different in important ways:
- [math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}
[/math] inputs entire strings, while [math]\href{/cs2800/wiki/index.php/%5Cdelta}{\delta}
[/math] inputs single characters
- Each automaton has its own definition of [math]\href{/cs2800/wiki/index.php/%5Cdelta}{\delta}
[/math]; the definition of [math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}
[/math] is the same for every automaton (although it depends on [math]\href{/cs2800/wiki/index.php/%5Cdelta}{\delta}
[/math]).
The definition of [math]\href{/cs2800/wiki/index.php/Delta_hat}{\hat{\delta}}
[/math] is different for different kinds of automata (DFA, NFA, etc). Here are their definitions:
Extended transition function for DFA
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].
Extended transition function for NFA
Extended transition function (NFA)
