Path function of a nfa, Theory of Computation

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

969_Path Function of a NFA.png

This just says that the path labeled ε from any given state q goes only to q itself (or rather never leaves q) and that to ?nd the set of states reached by paths labeled wσ from q one ?rst ?nds all the states q′ reached by paths labeled w from q and then takes the set of all the states reached by an edge labeled σ from any of those q′.

We will still accept a string w i? there is a path labeled w leading from the initial state to a ?nal state, but now there may be many paths labeled w from the initial state, some of which reach ?nal states and some of which do not. When thinking in terms of the path function, we need to modify the de?nition of the language accepted by A so it includes every string for which at least one path ends at a ?nal state.

Posted Date: 3/21/2013 2:35:52 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
Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL


The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

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

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

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

turing machine for prime numbers



constract context free g ={ a^n b^m : m,n >=0 and n