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
Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

can you plz help with some project ideas relatede to DFA or NFA or anything

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua


The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

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


The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat