Instantaneous description of an fsa, Theory of Computation

De?nition Instantaneous Description of an FSA:

An instantaneous description (ID) of a FSA A = (Q,Σ, T, q0, F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the portion of the input under and to the right of the read head.

w is the portion of the string remaining to be processed. The symbol being currently being read by the FSA is the ?rst symbol of w. If w is empty then the entire input has been scanned and the FSA has halted.

Posted Date: 3/21/2013 3:30:48 AM | Location : United States







Related Discussions:- Instantaneous description of an fsa, Assignment Help, Ask Question on Instantaneous description of an fsa, Get Answer, Expert's Help, Instantaneous description of an fsa Discussions

Write discussion on Instantaneous description of an fsa
Your posts are moderated
Related Questions
Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.



The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

how to convert a grammar into GNF

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh


Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

how to write program Minimum Cost Calculation - Vogel Approximation Method(VAM