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

Grammer, write grammer to produce all mathematical expressions in c. write grammer to produce all mathematical expressions in c.

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

Decision Theroy, spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8... spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

Class of local languages is not closed under union, Both L 1 and L 2 are ... Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

Turing machine, explain turing machine . explain turing machine .

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

Operator p, implementation of operator precedence grammer implementation of operator precedence grammer

Normal forms, how to convert a grammar into GNF how to convert a grammar into GNF

Kleene closure, So we have that every language that can be constructed from... So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Describe the algorithm and draw the transition diagram, 1. Simulate a TM wi... 1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization