Transition Monoid

Let δ : Σ × Q → Q : 𝛿 → Σ 𝑄 𝑄 \delta:\Sigma\times Q\to Q be a Semiautomaton over Σ Σ \Sigma . The transition monoid of δ 𝛿 \delta , denoted T ⁢ ( δ ) 𝑇 𝛿 T(\delta) is a Submonoid of the Endomorphism Monoid Q → Q → 𝑄 𝑄 Q\to Q , where f ∈ T ⁢ ( δ ) 𝑓 𝑇 𝛿 f\in T(\delta) if there exists some word u ∈ Σ ∗ 𝑢 superscript Σ u\in\Sigma^{*} such that f = δ ∗ ⁢ ( w , − ) 𝑓 superscript 𝛿 𝑤 f=\delta^{*}(w,-) , where δ ∗ superscript 𝛿 \delta^{*} is defined recursively as

δ∗⁢(ε,q)superscript𝛿𝜀𝑞\displaystyle\delta^{*}(\varepsilon,q) =qabsent𝑞\displaystyle=q
δ∗⁢(x⁢u,q)superscript𝛿𝑥𝑢𝑞\displaystyle\delta^{*}(xu,q) =δ∗⁢(u,δ⁢(x,q))absentsuperscript𝛿𝑢𝛿𝑥𝑞\displaystyle=\delta^{*}(u,\delta(x,q))

This can be viewed more abstractly: δ ∗ superscript 𝛿 \delta^{*} is a Monoid Action of the Free Monoid Σ ∗ superscript Σ \Sigma^{*} on Q 𝑄 Q , and the resulting monoid is the Transformation Monoid of this monoid action.