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
The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

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

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one


A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici