The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings:

Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an NFA with ε-transitions start by ?nding the set of states reachable from q using only ε-transitions and then, for each symbol σ of w (in order) ?nd the set of states reachable from those by an edge labeled σ and then the set of states reachable from those by any sequence of ε-transitions, etc.

Nothing else in the de?nitions need change. The automaton still accepts w if there is any computation on (q₀,w) that terminates in a ?nal state after scanning the entire input. Equivalently, it accepts w if there is a path labeled w from the initial state to a ?nal state, which is to say, if δ(q₀,w) includes any member of F. Note that the automaton of the example above will accept ‘ε' since state 2 is in ε-Closure(0) and, therefore in δ(0, ε).

Posted Date: 3/21/2013 2:49:26 AM | Location : United States

Ask an Expert

Related Discussions:- Path function of a nfa, Assignment Help, Ask Question on Path function of a nfa, Get Answer, Expert's Help, Path function of a nfa Discussions

Write discussion on Path function of a nfa
Your posts are moderated

Write your message here..

Related Questions

Find a regular expression, Find a regular expression for the regular langua... Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ... Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

Possibility of recognizing the palindrome language, Computer has a single F... Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

Qbasic, Ask question #Minimum 100 words accepte Ask question #Minimum 100 words accepte

Multitape turing machine, example of multitape turing machine example of multitape turing machine

Dddddddddddddd, wwwwwwwwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwww

Suffix substitution closure, Our primary concern is to obtain a clear chara... Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

Prepare the consolidated financial statements, Prepare the consolidated fin... Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

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

Kleenes theorem, All that distinguishes the de?nition of the class of Regul... All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat