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

Mealy machine, Construct a Mealy machine that can output EVEN or ODD Accord... Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

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

Complement - operations on languages, The fact that SL 2 is closed under i... The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

What is theory of computtion, what is theory of computtion what is theory of computtion

Intelligent computing, unification algorithm unification algorithm

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

Kleene closure, One might assume that non-closure under concatenation would... One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included

Fsa as generators, The SL 2 languages are speci?ed with a set of 2-factors... The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?} Σ and some factors in Σ {?} distinguishing symbols that may occur at the beginning and en

Computer architecture, What are the issues in computer design? What are the issues in computer design?

Automata, automata of atm machine automata of atm machine