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
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

Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

what problems are tackled under numerical integration

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


The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

Kleene called this the Synthesis theorem because his (and your) proof gives an effective procedure for synthesizing an automaton that recognizes the language denoted by any given r