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
#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

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.

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

DEGENERATE OF THE INITIAL SOLUTION

Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

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