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
shell script to print table in given range

Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(

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

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

design a turing machine that accepts the language which consists of even number of zero''s and even number of one''s?

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

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

What are the benefits of using work breakdown structure, Project Management