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

Differentiate between dfa and nfa, Differentiate between DFA and NFA. Conve... 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.

Operations on strictly local languages, The class of Strictly Local Languag... The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

Decidability, examples of decidable problems examples of decidable problems

REGULAR GRAMMAR, Find the Regular Grammar for the following Regular Express... Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Bit pair recoding, 20*2 20*2

Concatenation, We saw earlier that LT is not closed under concatenation. If... We saw earlier that LT is not closed under concatenation. If we think in terms of the LT graphs, recognizing the concatenation of LT languages would seem to require knowing, while

Abstract model of computation, When we say "solved algorithmically" we are ... When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

Gdtr, What is the purpose of GDTR? What is the purpose of GDTR?

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

Regular languages, LTO was the closure of LT under concatenation and Boolea... LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl