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

NP complete, I want a proof for any NP complete problem I want a proof for any NP complete problem

Finite-state automaton, Paths leading to regions B, C and E are paths which... 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

Nfas with e-transitions, We now add an additional degree of non-determinism... 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

Java programming, 1. An integer is said to be a “continuous factored” if it... 1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

Arden''s theoram, proof of arden''s theoram proof of arden''s theoram

Kleene Closure, 1. Does above all''s properties can be used to prove a lang... 1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

Automata and compiler, Automata and Compiler (1) [25 marks] Let N be the... Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

Design and implementation of the state machine, You are required to design ... 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

Myhill graphs, Another way of representing a strictly 2-local automaton is ... Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

Chomsky-schutzenberger, The upper string r ∈ Q+ is the sequence of states v... The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa