# Extended transition function

($1)$2 | $3 ($4) | $5 ($6)

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:

• inputs entire strings, while inputs single characters
• 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

Intuitively, when a DFA processes the empty string, it doesn't do anything: if it started in state , then it stays in state .

To process the string , the DFA would first process the substring , and then take one more step with the character (using the automaton's single step transition function).

This intuition leads to the following definition:

Given an DFA , we define the extended transition function inductively by , and .