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
Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

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

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea


Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with


Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat


You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur