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
Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to


The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

If the first three words are the boys down,what are the last three words??

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

De?nition Deterministic Finite State Automaton: For any state set Q and alphabet Σ, both ?nite, a ?nite state automaton (FSA) over Q and Σ is a ?ve-tuple (Q,Σ, T, q 0 , F), w


Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.