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


shell script to print table in given range

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

distinguish between histogram and historigram

DEGENERATE OF THE INITIAL SOLUTION


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

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r