Non deterministic finite state automaton, Theory of Computation

Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q0, Fi where Q, Σ, q0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}).

We must also modify the de?nitions of the directly computes relation and the path function to allow for the possibility that ε-transitions may occur anywhere in a computation or path. The ε-transition from state 1 to state 3 in the example, for instance, allows the automaton on input ‘a' to go from state 0 not only to state 1 but also to immediately go on to state 3. Similarly, it allows the automaton, when in state 1 with input ‘b', to move ?rst to state 3 and then take the ‘b' edge to state 0 or, when in state 0 with input ‘a', to move ?rst to state 2 and then take the ‘a' edge to state 3. Thus, on a given input ‘σ', the automaton can take any sequence of ε-transitions followed by exactly one σ-transition and then any sequence of ε-transitions. To capture this in the de?nition of δ we start by de?ning the function ε-Closure which, given a state, returns the set of all states reachable from it by any sequence of ε-transitions.

Posted Date: 3/21/2013 2:45:10 AM | Location : United States







Related Discussions:- Non deterministic finite state automaton, Assignment Help, Ask Question on Non deterministic finite state automaton, Get Answer, Expert's Help, Non deterministic finite state automaton Discussions

Write discussion on Non deterministic finite state automaton
Your posts are moderated
Related Questions
S-->AAA|B A-->aA|B B-->epsilon

The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

can you plz help with some project ideas relatede to DFA or NFA or anything

What is the purpose of GDTR?

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

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

s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?



Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the