my doubt is

what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ?

both of them when started at a state q for a string w will lead to same sate p what is the difference

is transition functions gives the transition over an input alphabet , where as the extended transition symbol gives a transition for the string w using the transition function?

  • 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 δ . Extended transition function : Describes what happens when we start in any state and follow any sequence of inputs ,means 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). denoted by ˆδ . in simple term : 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 of extended transition function :


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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