Editing Deterministic finite automaton (section)

==Formal definition==
A deterministic finite automaton {{mvar|M}} is a 5-[[n-tuple|tuple]], {{math|(''Q'', Σ, ''δ'', ''q''<sub>0</sub>, ''F'')}}, consisting of
* a finite [[Set (mathematics)|set]] of [[State (computer science)|states]] {{mvar|Q}}
* a finite set of input symbols called the [[Alphabet (computer science)|alphabet]] {{math|Σ}}
* a transition [[function (mathematics)|function]] {{math|''δ'' : ''Q'' × Σ → ''Q''}}
* an initial (or start) state <math>q_0 \in Q</math>
* a set of accepting (or final) states <math>F \subseteq Q</math>

Let {{math|1=''w'' = ''a''<sub>1</sub>''a''<sub>2</sub>...''a<sub>n</sub>''}} be a string over the alphabet {{math|Σ}}. The automaton {{mvar|M}} accepts the string {{mvar|w}} if a sequence of states, {{math|''r''<sub>0</sub>, ''r''<sub>1</sub>, ..., ''r<sub>n</sub>''}}, exists in {{mvar|Q}} with the following conditions:
# {{math|1=''r''<sub>0</sub> = ''q''<sub>0</sub>}}
# {{math|1=''r''<sub>''i''+1</sub> = ''δ''(''r<sub>i</sub>'', ''a''<sub>''i''+1</sub>)}}, for {{math|1=''i'' = 0, ..., ''n'' − 1}}
# <math>r_n \in F</math>.

In words, the first condition says that the machine starts in the start state {{math|''q''<sub>0</sub>}}. The second condition says that given each character of string {{mvar|w}}, the machine will transition from state to state according to the transition function {{mvar|δ}}. The last condition says that the machine accepts {{mvar|w}} if the last input of {{mvar|w}} causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton ''rejects'' the string. The set of strings that {{mvar|M}} accepts is the [[Formal language|language]] ''recognized'' by {{mvar|M}} and this language is denoted by {{math|''L''(''M'')}}.

A deterministic finite automaton without accept states and without a starting state is known as a [[transition system]] or [[semiautomaton]].

For more comprehensive introduction of the formal definition see [[automata theory]].