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
Ask queyystion #Minimum 100 words accepted#

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

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

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f


Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is