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

Non Regular, Prove that Language is non regular TRailing count={aa ba aaaa... Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

Sketch an algorithm to recognize the language, First model: Computer has a ... First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

First model of computation, Computer has a single unbounded precision count... Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

Merging nodes, Another striking aspect of LTk transition graphs is that the... Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

Automata, how to prove he extended transition function is derived from part... how to prove he extended transition function is derived from part 2 and 3

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

Closure properties of recognizable languages, We got the class LT by taking... We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

Flow charts, https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%... https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

Finiteness problem for regular languages, The fact that the Recognition Pro... The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

Xx, Ask queyystion #Minimum 100 words accepted# Ask queyystion #Minimum 100 words accepted#