Path function of a nfa, Theory of Computation

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

1132_Path Function of a NFA1.png

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 (q0,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 δ(q0,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







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
Related Questions
Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}

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

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

Ask question #Minimum 100 words accepte



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 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

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

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