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
conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}


i have some questions in automata, can you please help me in solving in these questions?

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

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

matlab v matlab

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

write short notes on decidable and solvable problem