Теорија на автоматите: Разлика помеѓу преработките

Еве три вида на конечни автомати

;[[детерминистичка конечна машина|Детерминистичка конечна машина]] ([[англиски јазик|англиски]] Deterministic finite automata (DFA)]]: Од секоја состојба на автоматите од овој тип има транзиција за секој симбол од азбуката.

; [[nondeterministic finite state machine|Nondeterministic finite automata (NFA)]] : States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from ''q''₀ to a state in F ''labeled'' with the input word. If a transition is ''undefined'', so that the automaton does not know how to keep on reading the input, the word is rejected.

; [[nondeterministic finite state machine|Nondeterministic finite automata, with ε transitions (FND-ε or ε-NFA)]] : Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with <math>\epsilon</math>, then the NFA can ''be'' in any of the states reached by the <math>\epsilon</math>-transitions, directly or through other states with <math>\epsilon</math>-transitions. The set of states that can be reached by this method from a state q, is called the <math>\epsilon</math>-closure of q.

It can be shown, though, that all these automata '''can accept the same languages'''. You can always construct some DFA M' that accepts the same language as a given NFA M.