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
1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second


Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph


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