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
conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}

what problems are tackled under numerical integration

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

How useful is production function in production planning?

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

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.

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1