Computation of a DFA or NFA without ε-transitions

An ID (q₁,w₁) computes (qn,wn) in A = (Q,Σ, T, q₀, F) (in zero or more steps)

if there is a sequence of IDs (q₁,w₁), . . . q_n,wn)) in which, for all i > 1,

A computation of an FSA A on input w is a computation from the initial ID (q₀,w) to a terminal ID: ((q₀,w_i, . . . , (q, ε)).

The fact that |-_A is no longer partial functional implies that we can no longer speak of the computation of A on hq1,w1i. What's more, while every computation is ?nite, it is no longer true that they all take exactly |w1| steps. Computations end when they reach an ID with no successor; this can now be either because the entire input was scanned or because an ID hq, σ
wi was reached for which δ(q, σ) = ∅. Only the ?rst case represents successful processing of w1 by A; we need to be careful to distinguish "halting" computations from those that "crash".

Posted Date: 3/21/2013 2:32:51 AM | Location : United States

Ask an Expert

Related Discussions:- Computation of a dfa or nfa, Assignment Help, Ask Question on Computation of a dfa or nfa, Get Answer, Expert's Help, Computation of a dfa or nfa Discussions

Write discussion on Computation of a dfa or nfa
Your posts are moderated

Write your message here..

Related Questions

Equivalence of nfas and dfas, In general non-determinism, by introducing a ... In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Normal forms, how to convert a grammar into GNF how to convert a grammar into GNF

Brain game, If the first three words are the boys down,what are the last th... If the first three words are the boys down,what are the last three words??

Applying the pumping lemma, Applying the pumping lemma is not fundamentally... Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Context free languages, how to find whether the language is cfl or not? how to find whether the language is cfl or not?

Perfect induction, A.(A+C)=A A.(A+C)=A

Discrete math, Find the Regular Grammar for the following Regular Expressio... Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Example of finite state automaton, The initial ID of the automaton given in... The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

Kleene closure, So we have that every language that can be constructed from... So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Grammer, write grammer to produce all mathematical expressions in c. write grammer to produce all mathematical expressions in c.