Extended transition function
The extended transition function of an automaton tells us what state ends up in after processing an entire string of characters. In fact, the definition of is what tells us what we mean when we say "process a string".
is similar to but different in important ways:
- strings, while inputs single characters inputs entire
- Each automaton has its own definition of ; the definition of is the same for every automaton (although it depends on ).
The definition of is different for different kinds of automata (DFA, NFA, etc). Here are their definitions:
Extended transition function for DFA
This intuition leads to the following definition: