Extended transition function

From CS2800 wiki

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)