What is the difference between transition function delta ($\delta$) and extended transition function delta hat ($\hat{\delta}$) in finite automata?

Both of them, when started at a state $q$ for a string $w$, will lead to the same state $p$. So what is the difference?

See, for example, page 15 of the third edition of Dexter Kozen's Automata and Computability (https://doi.org/10.1007/978-3-642-85706-5)

  • 1
    $\begingroup$ Please define the "extended transition function" -- it's not a concept I'm familiar with. And, I suggest that, if you write out the definition, the difference from the standard transition function should become obvious. $\endgroup$ Jun 22, 2019 at 10:23
  • $\begingroup$ Please edit the question to add a reference to the textbook or article you are talking about. $\endgroup$
    – John L.
    Jun 22, 2019 at 12:15

1 Answer 1


I read some references in order to answer your question.

  • Transition function: takes as arguments a state and an input symbol and returns a state, denoted by $\delta$.

  • Extended transition function: Describes what happens when we start in any state and follow any sequence of inputs. It is a function that takes a state $q$ and a string $w$ and returns a state $p$ (the state that the automaton reaches when starting in state $q$ and processing the sequence of inputs $w$). It is denoted by $\hat{\delta}$.

In simple terms: transition function takes two parameters: a state and a symbol, while extended transition function takes a state and a string.

Example of transition function

Example 1

Example of extended transition function

Example 2


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.