Extended transition function

From CS2800 wiki
Revision as of 02:53, 4 April 2020 by {{GENDER:Zis8|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)
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].

The first part of this definition says that processing the empty string doesn't move the machine; the second part says that to process [math]xa [/math], you first process [math]x [/math], and then take one more step using a from wherever [math]x [/math] gets you. Contrast the domain with that of [math]\delta [/math], which processes only a single character. This distinction is important: since [math]\delta [/math] only processes characters, its domain is finite, so the description of the machine is finite; but [math]\hat{\delta} [/math] (which is not part of the description of the machine) can process an infinite number of strings.