Path function of a nfa, Theory of Computation

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

1132_Path Function of a NFA1.png

Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an NFA with ε-transitions start by ?nding the set of states reachable from q using only ε-transitions and then, for each symbol σ of w (in order) ?nd the set of states reachable from those by an edge labeled σ and then the set of states reachable from those by any sequence of ε-transitions, etc.

Nothing else in the de?nitions need change. The automaton still accepts w if there is any computation on (q0,w) that terminates in a ?nal state after scanning the entire input. Equivalently, it accepts w if there is a path labeled w from the initial state to a ?nal state, which is to say, if δ(q0,w) includes any member of F. Note that the automaton of the example above will accept ‘ε' since state 2 is in ε-Closure(0) and, therefore in δ(0, ε).

Posted Date: 3/21/2013 2:49:26 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 initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

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


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

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

design an automata for strings having exactly four 1''s

Let G be a graph with n > 2 vertices with (n2 - 3n + 4)/2 edges. Prove that G is connected.

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

design a tuning machine for penidrome

These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third