Transition and path functions, Theory of Computation

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one state p such that hq, p, σi ∈ T. This function is called the transition function of the automaton and is usually denoted δ:

990_Transition and Path Functions.png

For any state q and symbol σ, then, δ(q, σ) is the state reached from q by following a single edge labeled σ. This can be extended to the path function, a function taking a state q and any string w ∈ Σ∗ which returns the statereached from q by following a path labeled w:

1907_Transition and Path Functions1.png

Note that ˆ δ is total (has some value for all q and w) and functional (that value is unique) as a consequence of the fact that δ is, which, in turn, is a consequence of the fact that the automaton is deterministic. In terms of the transition graph, this means that for any string w and any node q, there will always be exactly one path labeled w from q (which leads to δ(q,w)) and this is a consequence of the fact that there is always exactly one edge labeled σ from each node q of the graph and every σ ∈ Σ (which leads to δ(q, σ)).

Posted Date: 3/21/2013 3:35:56 AM | Location : United States







Related Discussions:- Transition and path functions, Assignment Help, Ask Question on Transition and path functions, Get Answer, Expert's Help, Transition and path functions Discussions

Write discussion on Transition and path functions
Your posts are moderated
Related Questions
A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

How useful is production function in production planning?

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif


For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be

De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

Ask question #Minimum 100 words accepte