Content deleted Content added
Citation bot (talk | contribs) Add: publisher, issue, isbn, authors 1-3. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Mathbot/Possible_redirects | #UCB_webform_linked 100/972 |
m →Formal definition: Unify formal definition with NFA |
||
Line 32:
==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
* a set of
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:
| |||