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
write grammer to produce all mathematical expressions in c.

build a TM that enumerate even set of even length string over a

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

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

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

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

i want to do projects for theory of computation subject what topics should be best.


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

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