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
Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones


Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

i have some questions in automata, can you please help me in solving in these questions?

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

Can v find the given number is palindrome or not using turing machine

Can you say that B is decidable? If you somehow know that A is decidable, what can you say about B?