Content deleted Content added
Adamant.pwn (talk | contribs) →History: missing "that" |
Adamant.pwn (talk | contribs) citations |
||
Line 40:
== Automaton structure ==
Formally, [[deterministic finite automaton]] is determined by [[5-tuple]] <math>\mathcal A = (\Sigma, Q, q_0, F, \delta)</math>, where:
* <math>\Sigma</math> is an "alphabet" that is used to construct words,
Line 48:
* <math>\delta : Q \times \Sigma \mapsto Q</math> is a [[Partial function|partial]] "transition" function of automaton, such that <math>\delta(q, \sigma)</math> for <math>q \in Q</math> and <math>\sigma \in \Sigma</math> is either undefined or defines a transition from <math>q</math> over character <math>\sigma</math>.
Most commonly, deterministic finite automaton is represented as a [[directed graph]] ("diagram") such that:<ref name=":14">{{harvp|Серебряков и др.|2006|loc=|pp=50—54}}</ref>
* Set of graph [[Vertex (graph theory)|vertices]] corresponds to the state of states <math>Q</math>,
Line 263:
# Transitions that have lead to <math>q</math> before but corresponded to words of the length at most <math>len(p)+1</math> are redirected to <math>cl</math>. To do this, one continues going through the suffix path of <math>p</math> until the state is found such that transition by <math>x</math> from it doesn't lead to <math>q</math>.
The whole procedure is described by the following pseudo-code:
'''function''' {{mvar|add_letter(x)}}:
Line 284:
'''assign''' {{mvar|δ(p, x) {{=}} cl, p {{=}} link(p)}}
Here <math>q_0</math> is the initial state of the automaton and <math>new\_state()</math> is a function creating new state for it. It is assumed <math>last</math>, <math>len</math>, <math>link</math> and <math>\delta</math> are stored as global variables.
=== Complexity ===
| |||